[백준 2018] 수들의 합 5

투 포인터를 사용하여 해결할 수 있는 전형적인 문제입니다.

Key Point

본 문제에서 주목할만한 점은 다음과 같습니다.

• 투 포인터를 사용하여 해당 구간의 합이 n보다 크면 start 포인터를 움직이고,
  n보다 작거나 같으면 end 포인터를 움직입니다.

해결방법

투 포인터를 사용하는 전형적인 문제입니다.
start, end 라는 두 개의 포인터를 모두 1로 초기화하여 설정하고,
해당 구간 수들의 합을 저장해놓을 total 이라는 변수도 1로 초기화하며 (현재 start와 end 모두 1이므로)
가짓수 즉, 답을 저장해놓을 cnt 변수 또한 1로 미리 초기화합니다. (n 자기 자신이 하나의 가짓수이므로)

예를 들어 n = 15 라고 하면

[1] 2 3 4 5 6 7 8 9 10 11 12 13 14 15     total = 1

현재 구간은 괄호로 이루어진 구간입니다.
이때, total = 1 < 15 이므로 end 포인터를 1 늘리고 total에 더합니다.

[1 2] 3 4 5 6 7 8 9 10 11 12 13 14 15     total = 3

다시 total = 3 < 15 이므로 또다시 end 포인터를 1 늘리고 total에 더합니다.

[1 2 3] 4 5 6 7 8 9 10 11 12 13 14 15     total = 6

위 과정을 계속 반복하다보면

[1 2 3 4 5] 6 7 8 9 10 11 12 13 14 15     total = 15

total = 15 = n 이 되는 경우가 발생합니다.
바로 이때, 답에 1을 추가하고 start 포인터를 total에서 빼고 1 늘려서 당깁니다.

1 [2 3 4 5] 6 7 8 9 10 11 12 13 14 15     total = 14

이후에는 end 포인터가 n이 되기 전까지 계속해서 반복하면 됩니다.

아래의 3가지 규칙에 주목합시다.

• total = n 이면, end + 1, total + end, cnt + 1
• total > n 이면, total - start, start + 1
• total < n 이면, end + 1, total + end

코드는 아래와 같습니다.
문제 : 백준 2018 - 수들의 합 5