2018번: 수들의 합 5
어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한
www.acmicpc.net
문제
어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.
예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.
N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.
입력
첫 줄에 정수 N이 주어진다.
출력
입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오
코드
n = int(input())
left, right = 0, 1
ans = 0
total = 1 # left~right 구간의 수들의 합
while left <= n:
if total == n:
ans += 1
left += 1
right += 1
total = (total-(left-1)+right)
elif total < n:
right += 1
total += right
else:
total -= left
left += 1
print(ans)
처음에는 DP로 푸는 방법을 생각했는데, 연속된 수들의 합으로 만들어야 하기 때문에 DP로 하면 연속된 수로 만들어지는지 구하기 어려울 것 같아서 투포인터로 바꿨다.
left와 right는 합을 구할 구간의 시작과 끝이다. left와 right도 구간에 포함된다. total은 left부터 right까지의 수들의 합이다.
- total == n : ans의 값을 1 증가시키고, left와 right를 오른쪽으로 하나씩 옮겨준다.
- total < n : 더 많은 수가 필요한 것이므로 right를 1 증가.
- total > n : 구간에 포함되는 수를 줄여야하므로 left를 1 증가.
'문제풀이 > 투포인터' 카테고리의 다른 글
[Python/파이썬] 백준 11687번 팩토리얼 0의 개수 (0) | 2024.02.25 |
---|---|
[Python/파이썬] 백준 2559번 수열 (0) | 2024.01.31 |
[Python/파이썬] 백준 2003번 수들의 합 2 (1) | 2023.12.05 |
[Python/파이썬] 백준 14921번 용액 합성하기 (0) | 2023.08.28 |
[Python/파이썬] 백준 20442번 ㅋㅋ루ㅋㅋ (0) | 2023.06.05 |