[백준 2018] 수들의 합

1. 링크

https://www.acmicpc.net/problem/2018

2. 문제 설명

(1) 문제

어떠한 자연수 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을 입력받아 가지수를 출력하는 프로그램을 작성하시오.

 

(2) 입력

첫 줄에 정수 N이 주어진다.

 

(3) 출력

입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오

 

3. 코드

#2018

import sys

#입력 받기
N = int(sys.stdin.readline().strip())

#투 포인터 사용
count = 1
start_index = 1
end_index = 1
sum = 1

while end_index < N:
    if sum == N:
        count += 1
        end_index += 1
        sum += end_index
    
    elif sum > N:
        sum -= start_index
        start_index += 1

    else:
        end_index += 1
        sum += end_index

print(count)

4. 설명

투 포인터를 활용한 문제이다. 1부터 N까지의 루프에서 start_index와 end_index로 두 가지 포인터를 놓고, 두 포인터 사이의 값을 합했을 때(sum) N이 된다면 count가 증가하고 end_index가 증가한다. 만약 sum이 N보다 크다면 sum에서 start_index를 빼고 start_index를 1 증가시킨다. 이는 start_index 부분의 수를 sum에서 빼고 다른 연속된 합을 찾는 것이다. 만일 N이 sum보다 작다면 end_index를 증가시키고 sum에 그만큼 더한다.

5. 배운 점

투 포인터 챕터의 첫 문제이다. 아직도 포인터 하면 C언어의 악몽이 떠올라서...ㅎㅎ 처음에 지레 겁 먹었지만 교재를 찾아가면서 풀어낼 수 있었다. 생각보다 원리도 어렵지 않고 간단한 코드여서 다음에는 유사한 문제를 자력으로 풀어보고 싶다.