[백준][Python] 2018 수들의 합 5

투포인터 / 실버 5

🔢

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

2018번: 수들의 합 5

 

내 풀이

N = int(input())
num = [x for x in range(1, N+1)]
s, e = 0, 1
ans = 0

while s < e and s < N // 2:
    current = sum(num[s:e])
    if current < N:
        e += 1
    elif current > N:
        s += 1
    else:
        s += 1
        e = s + 1
        ans += 1
    
print(ans + 1)

 

 

코드 설명

 

투포인터로 풀었다.

시작 인덱스(s)가 끝 인덱스(e) 보다 작고, 시작 인덱스(s)가 N // 2보다 작은 경우 반복문을 실행한다.

 

N = 15라고 할 때,

정답은 4가지(1+2+3+4+5, 4+5+6, 7+8, 15)이다.

 

7 + 8인 경우를 살펴보면,

s = 6, e = 7이다.

숫자의 합과 N이 일치하므로, else문이 실행되며,

s = 7, e = 8이 되고, current 값은 8 + 9 = 17이 된다.

 

여기서 알 수 있는 것은 s가 N // 2 (여기서는 7) 이상이 되면,

두 개 이상의 연속된 자연수의 합이 N과 같아질 수가 없다.

무조건 N보다 크다는 것이다.

 

따라서, 굳이 끝까지 검사할 필요가 없다.

 

다만, 자연수 N(자기 자신)으로만 조합하는 경우가 존재하기 때문에

반복문이 끝나고 정답(ans)에 1을 더해주면 된다.