728x90
2018번: 수들의 합 5
어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한
www.acmicpc.net
분석
[2003] 수들의 합2 (투 포인터)
2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmic
karla.tistory.com
풀이
"""
어떠한 자연수 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=int(input())
# 투 포인터
l=1
r=1
cnt=1 # n이 15일 때 숫자 15만 뽑는 경우의 수 미리 넣고 초기화
sum=1
while r!=n:
print(l, r, sum)
if sum==n: # 정답케이스
cnt+=1
# 계속 진행해야 하기 때문에
r+=1
sum+=r
elif sum>n:
sum-=l
l+=1
else:
r += 1
sum+=r
print(cnt)
728x90