[ProblemSolving] 백준 - 1806 부분합(투포인터)

문제 링크

문제 설명

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

예제 입력1

10 15
5 1 3 5 10 7 4 9 2 8

예제 출력1

2

나의 풀이

이 문제는 투포인터를 이용한다

투 포인터란 구간의 값이 타겟 값과 같아질 때까지 포인터를 조작하는 기법이다.

left 시작점과 right 도착점을 기준으로,

• 타겟값보다 작다면 right을 1증가
• 타겟값보다 크다면 left를 1감소

동작

1. right를 하나씩 이동하면서 temp에 누적

2. temp값이 s이상이라면
   result에 최소 길이 구해주고
   temp에서 left 빼고, left 오른쪽으로 한칸 이동

3. right가 배열의 끝에 다다를 때까지 반복

코드

n, s = map(int, input().split())
arr = list(map(int, input().split()))

left, right = 0, 0
temp = 0
result = n+1

while True:

    # 크거나 같으면 최소 길이 구한다
    if temp >= s:
        result = min(result, right-left)
        temp -= arr[left]
        left += 1

    elif right == n:
        break

    else:
        temp += arr[right]
        right += 1

if result == n+1:
    print(0)
else:
    print(result)