[백준 2018] 연속된 자연수의 합 구하기 feat 투포인터

Status

Published

입력

첫 줄에 정수 N이 주어진다.

출력

입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오

www.acmicpc.net

어떤 자연수 N이 주어졌을 때,

이걸 연속된 자연수의 합으로 표현하는 방법의 수를 구하라.

예를 들어 N=15면

15 = 15

15 = 7+8

15 = 4+5+6

15 = 1+2+3+4+5

답 : 4

냅다 풀기

연속된 자연수의 합? ← 어떠한 배열속에 연속된 수들의 합? → 구간합, 누적합 문제인가?

N=15라면


[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...]

이렇게 자연수가 쭉 늘어선 배열이 있는거고 그중에 연속된 구간의 합이 N이 되는걸 찾기

구간합 → 누적합? 이라고 하기엔 뭔가 비효율적 같은 느낌이 들었다.

모든 경우의수를 다 봐야한다.


i=1: 1+2+3+4+5 = 15 o
i=2: 2+3+4+5 = 14 x  
i=3: 3+4+5 = 12 x 
i=4: 4+5+6 = 15 o  
i=5: 5+6+7 = 18 x  
i=7: 7+8 = 15 o  
i=15: 15 o


N = int(input())
count = 0

for i in range(1, N+1):
    sum = 0
    for j in range(i, N+1):
        sum += j
        if sum == N:
            count += 1
            break
        if sum > N:
            break

print(count)

2중 for문 구조로 • O(N²) 이란 시간복잡도가 나온다… n에 1,000,000을 넣으면 터진다. 흠… 어떻게 풀어야할까?

필요한 개념

어떤 배열에서 연속된 구간의 합이 N이 되는 경우를 찾기

부분합, 누적합 (저번 포스터) 참고

투 포인터

정렬된 배열에서 효율적으로 구간 찾기

sum < 목표	end 포인터 오른쪽으로 이동
sum > 목표	start 포인터 오른쪽으로 이동
sum == 목표	정답 + start 포인터 이동

투포인터 개념에서도 다양한 다른 개념이 있지만.

문제 적용하기

1~15까지의 연속된 자연수 중에서 어떤 연속된 부분합이 15가 되는지 투포인터를 사용하여 찾는 과정을 예로

아래 상황을 구체적으로 보면서 이해한다면 투포인터가, 어떻게 동작하는지 원리를 정확하게 알 수 있다.

초기상태에서 start , end 포인터의 인덱스 번호들이 움직이고있다.

아래의 표의 상황에 맞게 움직이는 중이다.

sum > 목표	Start 포인터 오른쪽으로 이동
sum == 목표	count 1증가 후 Start 포인터 이동

이 후 sum > 목표 인 경우 end포인터가 오른쪽으로 이동 하면서 sum이 줄어든다. 이 과정 중 다시 sum이 목표와 값이 같을경우 count를 증가시키고 다시 start포인트를 이동시킨다.

목표값 보다 현 총합(sum)이 클때

end 포인트가 이동하면서 값을 줄이는 방식…반복하면 된다.

정리하면 아래와 같다.


[1] sum < 목표값 → end_index++
[2] sum > 목표값 → start_index++
[3] sum == 목표값 → count++ 후 start_index++

해당 알고리즘을 사용하여 O(N)의 시간복잡도를 가지며 배열을 한 번 훑으면서 해결 가능하다.

이제 이 개념을 가지고 슈도코드를 작성 후 마무리 해보자.


입력 N

# 포인터와 변수 초기화
start = 1          # 구간의 시작 숫자
end = 1            # 구간의 끝 숫자
sum = 1            # 현재 구간의 합 (start ~ end)
count = 0          # 조건을 만족하는 경우의 수

# 반복 시작
while start <= N:

    # 현재 구간의 합이 N과 같을 때
    if sum == N:
        count += 1          # 경우의 수 1개 추가 (정답)

    # 현재 합이 목표값보다 크거나 같으면
    if sum >= N:
        sum -= start        # start 포인터의 값을 빼고
        start += 1          # start 포인터를 오른쪽으로 이동

    # 현재 합이 목표값보다 작으면
    else:
        end += 1             # end 포인터를 오른쪽으로 이동
        sum += end           # end 값을 합에 추가

# 결과 출력
출력 count


N = int(input())  # 입력 받기

# 포인터 및 변수 초기화
start = 1
end = 1
sum = 1
count = 0

while start <= N:

    if sum == N:
        count += 1  # 경우의 수 하나 추가

    if sum >= N:
        sum -= start  # 구간의 첫 번째 값을 빼고
        start += 1    # 시작 포인터 이동

    else:
        end += 1      # 끝 포인터 이동
        sum += end    # 새로운 값을 합에 추가

print(count)