[백준] 2018번 : 수들의 합 5 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

2018번: 수들의 합 5

 

1. 문제 설명

2. 풀이과정

문제에서 주어진 시간 제한은 2초인데 N의 최댓값은 10,000,000으로 매우 크게 잡혀있다.

이러한 상황에서는 O(n)의 시간 복잡도 알고리즘을 사용해야 한다.

연속된 자연수의 합을 구하는 것이 문제이므로, 시작 값과 끝 값을 지정하여 연속된 수를 표현한다. (투 포인터)

 

시작 값과 끝 값을 모두 1로 두고 연속된 자연수의 합도 1로 저장한다.

두 위치를 끝까지 이동하면서 합이 N이 되는 경우의 수를 구한다.

N이 경우의 수에 포함되므로 경우의 수는 1로 시작한다.

만약 합이 N이면, 끝 값을 1 증가시키고 합도 변경한다. (합이 N이 되는 경우이므로 경우의 수도 증가시킨다.)

만약 합이 N을 넘어가면, 시작 값을 1 증가시키고 합도 변경한다.

만약 합이 N 이전이면, 끝 값을 1 증가시키고 합도 변경한다.

 

슈도코드

1. N 변수 입력받기
2. 사용할 변수 초기화 (start = 1, end = 1, answer = 1, SUM = 1)
3. while (end != N)
4. if (SUM == N) : 경우의 수 증가, end 증가, SUM + end
5. elif (SUM > N) : SUM - start, start 증가
6. else : end 증가, SUM + end

반응형

3. 소스코드

import sys

N = int(sys.stdin.readline())

start = 1
end = 1

answer = 1
SUM = 1
while (end != N):
    if (SUM == N):
        answer += 1
        end += 1
        SUM += end
    elif (SUM > N):
        SUM -= start
        start += 1
    else:
        end += 1
        SUM += end
        
print(answer)