백준 1806 부분합 (골드 4)

백준 1806 부분합 (골드 4)

링크: 1806 부분합

---

접근 방법

• 뱀게임처럼 deque로 관리해서 계산
• (도움) 두 포인터로 구간합을 계산해서 최소값 기록

---

소스 코드

소스 코드: 구간합 알고리즘

from collections import deque

# 우선순위: S를 넘은 것, 길이가 짧은 것, 합이 큰 것(0 으로 처리), 길이가 짧은 것
N, S = map(int, input().split())
num_list = [int(i) for i in input().split()]

start_idx = 0
end_idx = 0
num_sum = 0
min_length = float('inf')
while end_idx < N:
    if num_sum < S:
        num_sum += num_list[end_idx]
        end_idx += 1

    if num_sum >= S:
        while num_sum >= S:
            num_sum -= num_list[start_idx]
            start_idx += 1

        min_length = min(min_length, end_idx - start_idx + 1)

print(min_length if min_length != float('inf') else 0)

---

코드 개선 사항(GPT 4o)

• 없음

결론

• 최근 뱀게임 시뮬레이션 문제를 풀어서 접근 자체는 괜찮았는데, 두포인터라는 방식이 있던 것을 까먹었었다.
• 아쉽다...