https://www.acmicpc.net/problem/2018
2018번: 수들의 합 5
어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한
www.acmicpc.net
처음 이 문제를 보았을때, dp를 사용해야 하나 싶었다. 그러나 dp로는 단순히 연속된 수들만 구할 수 있었고, 그 다음으로 생각한 것이 브루트 포스였다.
하지만 n이 10,000,000개라는 점에서 브루트 포스 또한 초과가 나올 것이 분명했다.
그래서 투포인터로 풀어야겠다 생각했다.
n = int(input())
arr = [i for i in range(1, n+1)]
answer = 0
end = 1
start = 0
while start <= end and end < n:
s = sum(arr[start:end + 1])
if s == n:
end += 1
answer += 1
elif s < n:
end += 1
elif s > n:
start += 1
print(answer)처음 투포인터로 작성한 코드다.
하지만 메모리 초과가 나왔다.
아마 sum으로 arr의 구간 합을 구할 때 메모리 초과가 나왔을 것이라 생각했고 아래와 같이 수정하였다.
n = int(input())
answer = 0
s = 0
start, end = 0, 0
while end <= n:
if s < n:
end += 1
s += end
elif s > n:
s -= start
start += 1
elif s < n:
answer += 1
end += 1
s += end
print(answer)