[python/파이썬] 백준 2018 수들의 합 5 .

[문제 출처]

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

2018번: 수들의 합 5

 

[소스 코드1 - 시간 초과]

 

생각나는대로 그냥 풀어봤더니 역시나 시간 초과가 나왔다.

import sys
input = sys.stdin.readline

n = int(input())

cnt = 0
for i in range(1,n+1):
    sum = 0
    for j in range(i,n+1):
        sum += j
        if sum == n:
            cnt += 1
            break

print(cnt)

 

[소스 코드2 - 메모리 초과]

 

import sys
input = sys.stdin.readline

n = int(input())
arr = [i for i in range(1, n+1)]

sum, end = 0, 0
cnt = 0

for i in range(n):
    while end < n and sum < n:
        sum += arr[end]
        end += 1
    if sum == n:
        cnt += 1
    
    sum -= arr[i]

print(cnt)

 

[소스 코드3 - 틀렸습니다]

 

리스트가 문제인 것 같아서 없애보았는데 이번엔 틀렸다.

리스트만 없앤다는게 잘못 건드린 것 같다.

import sys
input = sys.stdin.readline

n = int(input())

sum, end = 0, 1
cnt = 0

for i in range(1,n+1):
    while end < n and sum < n:
        sum += end
        end += 1
    if sum == n:
        cnt += 1
    
    sum -= i

print(cnt)