[백준 1806 파이썬] 부분합 (골드 4, 투 포인터)

알고리즘 유형 : 투 포인터
풀이 참고 없이 스스로 풀었나요? : O

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline

N, S = map(int, input().split())
arr = list(map(int, input().split())) + [0]

# 투 포인터를 모두 왼쪽에 위치
i=0
j=0
# 최소 길이를 담는 변수. 계속 갱신해줄거임
result = float('inf')
# 부분합을 담아두는 변수. S 이상인지 판단하기 위함
subtotal = arr[i]

# 오른쪽 포인터가 범위를 벗어나면 종료
# 맨 왼쪽부터 오른쪽까지 부분 수열을 키워나가면서
# 부분합이 S 이상인 부분 수열을 모두 검토할 수 있음
while j < N:
    # 두 포인터 사이의 부분합이 S 이상이면
    # result를 비교&갱신해주고, 배열에서
    # 오른쪽 포인터까지의 부분 범위에서
    # S 이상임을 만족하는 부분 수열의
    # 최소 길이를 최대한 찾아줘야하므로
    # 오른쪽 포인터를 유지하고 왼쪽
    # 포인터를 오른쪽으로 한 칸 이동하여
    # S 이상인지 검사
    # 만약 길이가 1이면 가능한 최소의 값이므로
    # 바로 break
    if subtotal >= S:
        sub_len = j-i+1
        result = min(result, sub_len)
        if sub_len == 1:
            break
        subtotal -= arr[i]
        i += 1
    # S 이하이면 부분합을 더 키워야하므로
    # 오른쪽 포인터 한 칸 이동
    else:
        j += 1
        subtotal += arr[j]
        
if result == float('inf'):
    print(0)
else:
    print(result)

풀이 요약

1. 전형적인 투 포인터 문제이다.

2. 투 포인터를 모두 왼쪽에 두고, 부분 수열을 오른쪽 방향으로 키워나가면서 부분합이 S 이상인 부분 수열을 모두 검토해볼 수 있다.

3. 현재 투 포인터 사이의 부분 수열에 대해, 부분합이 S 이상이면 그 때의 길이를 result에 비교&갱신해두고, 왼쪽 포인터를 한 칸 이동하여 부분 수열을 줄여준다. 오른쪽 포인터의 현 위치에 대해 가능한 모든 S 이상의 부분 수열을 고려하고자 하는 것이다.

   만약 부분합이 S 이상인데 길이가 1이라면 그게 이론상 가능한 최소한의 길이이므로 바로 break해주고 정답을 출력해준다.

   한편, 부분합이 S 미만이면 더 키워야하므로 오른쪽 포인터를 한 칸 진행한다.

4. 오른쪽 포인터가 범위를 벗어날 때 까지 반복한다. 이 때까지 부분합이 S 이상인 부분 수열이 한번도 없었다면 result에는 float('inf')가 저장되어있다.

배운 점, 어려웠던 점

• 투 포인터 활용력을 기를 수 있는 간단한 문제였다.