[2018]연속된 자연수의 합 구하기.py

투 포인터

• O(n)의 시간 복잡도 알고리즘을 사용하기 위해 투 포인터를 사용.
• 시작 인덱스와 종료 인덱스를 지정해 연속된 수를 표현.

투 포인터 이동 원칙

• sum > N: sum = sum - start_index; start_index++;

• sum < N: end_index++; sum = sum + end_index;

• sum == N: end_index++; sum = sum + end_index; count++;

• start_index를 오른쪽으로 한 칸 이동하는 것은 연속된 자연수에서 왼쪽 값을 삭제하는 효과

• end_index를 오른쪽으로 한 칸 이동하는 것은 연속된 자연수의 범위를 한 칸 더 확장하는 의미

• 같을 때는 경우의 수를 1 증가시키고, end_index를 오른쪽으로 이동

# n: 입력된 자연수
n = int(input())

# 사용 변수 초기화
# count: 결과 변수
# start_index / end_index: 시작/종료 인덱스
# sum: 자연수의 합
count = 1
start_index = 1
end_index = 1
sum = 1

while end_index != n:
    if sum == n:
        count+=1
        end_index+=1
        sum = sum+end_index
    elif sum > n:
        sum = sum - start_index
        start_index+=1
    else:
        end_index+=1
        sum=sum+end_index

print(count)

• count를 1로 초기화: N이 15일 때 숫자 15만 뽑는 경우으 ㅣ수를 미리 넣고 초기화 했기 때문