[백준 - Python] 1806. 부분합

https://www.acmicpc.net/problem/1806

 

코드

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

start, end = 0, 0

sum_ = arr[0]
# 수 범위 보고 적절한 최댓값으로 설정하기
ans = 100001

while True:
    if sum_ < s:
        end += 1
        if end == n:
            break
        sum_ += arr[end]
    else:
        ans = min(ans, end-start + 1)
        sum_ -= arr[start]
        start += 1
    # 가장 길이가 짧은 것을 구하는 문제라 가능한 모든 경우를 훑은 코드가 되는 것인지?

print(ans if ans != 100001 else 0)

 

접근 방식

1. 투포인터를 사용하기 위해서는 수열을 정렬해야겠다고 생각 

2. 포인터를 각각 0으로 초기화

3. 합이 s보다 작은 경우, 끝 포인터를 이동 및 부분합에 더하기

3. 합이 s 이상인 경우, 최솟값 갱신해주고 시작 포인터 이동 및 부분합에서 빼기

4. end == n일 때 반복문 탈출 (즉, 모든 경우 확인 후 종료)

 

배운 점

1. 투포인터로 풀어야 한다는 생각은 어떻게 하나?

    - 배열의 길이가 최대 100,000이므로, 완전 탐색 기법(O(N))은 불가능하니 다른 풀이법 생각

    - `연속된 부분 수열의 합` 문제는 투포인터 혹은 슬라이딩 윈도우와 같은 효율적 접근법 필요

        (`연속된 부분 수열의 합` 문제를 하나의 투포인터 유형으로 생각)

    - 투포인터 기법은 배열을 순회하며 조건을 만족하는 부분을 효율적으로 찾을 수 있다는 특징 고려

 

2. 투포인터 방식이 이진 탐색이랑 혼동되면서 꼭 포인터를 배열의 양끝에 둬야 한다고 생각했는데, 그렇지 않다

3. 투포인터의 핵심은 조건에 따라 포인터를 이동시키면서 최적해를 찾는 것