(Python/파이썬) - 백준(BOJ) 2018번 : 수들의 합 5

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

2018번: 수들의 합 5

---

• 문제 : 

어떠한 자연수 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을 만들 수 있는 경우를 찾으면 됩니다.

 

알고리즘의 흐름입니다.

 

1. left와 right를 설정. (둘 다 0으로 해도 되지만 저는 0,1로 설정하고 누적값인 acc의 초깃값을 1로 하였습니다.)

 

2. left가 right보다 작거나 같은 동안 진행합니다. left가 right보다 커졌을 경우 반드시 N을 초과한 상태이므로 이는 올바른 분기점입니다.

 

3. 세 가지 경우가 있습니다.

 

- acc(누적값)이 N과 같은 경우 -> 정답 카운트를 1증가시키고 right를 1 증가시킵니다. 또한 acc에 right값을 더해줍니다. 

 

- acc가 N보다 작은 경우 -> left를 늘리면 acc는 감소하므로 right를 증가시키고 그 값을 acc에 더해줍니다. (acc == N 일때와 동일)

 

- acc가 N보다 큰 경우 -> left를 늘려 acc를 감소시켜야 합니다. acc에서 left값을 빼고 left를 1 증가시킵니다.

 

 

 

주의할 점 ) acc > N일 땐 acc에서 left를 먼저 빼고 left를 1 증가시켜야 하고 반대의 경우 (acc <= N) 일 땐, right를 1 증가시키고 acc에 더해주어야 합니다. (중복 덧셈or 뺄셈 방지용)  

 

 

참고 ) N이 최대 10,000,000이므로 O(N) 이상의 시간복잡도를 가진 풀이를 사용할 경우 ex)완전탐색 등

시간초과가 나오니 주의해야 합니다.

 

 

---

• 소스코드 : 

left = 0
right = 1
answer = 0
acc = 1
N = int(input())
while left <= right:
    if acc == N:
        answer += 1
        right +=1
        acc += right
    elif acc < N:
        right += 1
        acc += right
    elif acc > N:
        acc -= left
        left += 1
print(answer)