[백준] 2018 파이썬(python) : 수들의 합 5

2018번 : 수들의 합 5

 

 

import sys
n = int(sys.stdin.readline())
start, end = 0, 0
cnt, tmp = 0, 0

while end <= n: #1
    if tmp < n: #2
        end += 1
        tmp += end
    elif tmp > n: #3
        tmp -= start
        start += 1
    else: #4
        cnt += 1
        end += 1
        tmp += end
print(cnt)

 

#1 : end포인터가 n의 값을 초과하지 않을때까지 반복

#2 : 현재 누적값이 n보다 작을때 end포인터 1증가 후 현재값에 누적합

#3 : 현재 누적값이 n보다 클때 start포인터의 값을 누적값에서 뺀뒤 start포인터 증가

#4 : 누적값과 n이 같은 경우 cnt 1증가 end포인터 1증가 그리고 누적값에 end포인터의 값 추가

(이 다음 #3이 수행될것)

 

O(n^2)로 풀면 시간초과가 나기에 투 포인터 알고리즘을 사용해야한다.

 

다른풀이)

import sys
n = int(sys.stdin.readline())
number = list(range(1, n+1))
start, end = 0, 0
tmp, cnt = number[0], 0
while end <= n-1: #1
    if tmp < n:
        end += 1
        if end >= n:
            break
        tmp += number[end]
    elif tmp > n:
        tmp -= number[start]
        start += 1
    else:
        cnt += 1
        tmp -= number[start]
        start += 1
print(cnt)

 

#1 : "while True:"로 바꿔도 괜찮다.

 

---

2003 : 수들의 합 2