[백준 1806] 부분합

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

Key Point

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

• 투 포인터를 사용하여 포인터 범위 사이에 있는 연속된 숫자들의 합이 기준 s 이상이면 start 포인터를 +1 처리하고, s보다 작으면 end 포인터를 +1 처리하면 됩니다.

해결방법

투 포인터를 사용해봅시다.
수열의 길이가 최대 10만이므로 이를 고려하여 O(n) 내에 수행되도록 작성합시다.
start, end 라는 두 개의 포인터를 ‘인덱스’ 라고 생각하고 각각 0으로 초기화합니다.
수열에서 start와 end 인덱스 범위 사이에 있는 수들의 합에 따라 포인터를 움직입니다.

수들의 리스트를 nums라고 하고 답을 저장하는 변수를 ans라고 할 때, 아래의 규칙에 주목합시다.
매번 포인터를 옮길 때마다 범위를 full scan해서 합을 구하면 시간 복잡도가 늘어나므로
O(n) 내에 수행될 수 있도록 합을 담아둘 변수 total을 설정합니다.

• total >= s 이면, ans = min(ans, end - start + 1), start += 1
• total < s 이면, end += 1

위의 과정을 (start <= end < 수열의 길이 n)이 성립하는 동안 계속 반복하면 됩니다.

코드는 아래와 같습니다.
문제 : 백준 1806 - 부분합