문제 출처 : https://www.acmicpc.net/problem/1806
난이도 : 골드 4

---

문제 파악

입력으로 길이 N인 수열이 주어지고,
“연속된” 부분 수열(= 구간)을 골라서
그 구간의 합이 S(target) 이상인 것들 중
가장 짧은 길이를 출력해야 한다.
조건을 만족하는 구간이 없다면 0을 출력한다.

투 포인터 문제는 정렬을 하고 진행하는데 이 문제는 순서가 중요하기에 정렬을 해선 안된다.

그러면 어떻게 풀어야 할까?

문제에 이런 힌트가 숨어 있었다.

수열 원소가 전부 자연수(양수)

양수면 어떤 일이 생기냐?
right를 늘리면 구간에 숫자가 추가되니까 total이 절대 감소하지 않음
left를 늘리면 구간에서 숫자가 빠지니까 total이 절대 증가하지 않음

그래서 “합이 target 이상이 되는 순간”을 찾고, 그 상태에서 left를 줄여서 최소 길이를 뽑아내는 전략이 성립한다.

해결 아이디어

구간을 [left, right) 로 잡자. (right는 포함 안 함)

total < target 이면: 아직 합이 부족 → right를 늘려서 합 키우기
total >= target 이면: 조건 만족! → 길이 후보 갱신 후 left를 늘려서 더 짧아질 수 있는지 확인

이걸 right가 끝까지 갈 때까지 반복하면,
가능한 모든 “연속 구간”을 빠짐없이 확인한 거랑 같다.

해답 및 풀이

import sys
input = sys.stdin.readline

N, target = map(int,input().split())

nums = list(map(int,input().split()))

INF = float("inf")
answer = INF # 가장 짧은것을 구해야 하니 가장 큰 것으로 초기화

left = 0
right = 0
total = 0 # 구간 합 [left, right)

while True:
    if total >= target:
        answer = min(answer, right-left)
        total -= nums[left]
        left += 1
    else:
        if right == N: # 더 이상 늘릴 수 없음
            break
        total += nums[right]
        right += 1

print(0 if answer == INF else answer)

---

위 방법으로 푸니 [left,right) 이기에 뭔가 익숙하지 못했다.

[left,right] 구간으로 풀고 싶으면 다음 코드로 풀 수 있다.

import sys
input = sys.stdin.readline

INF = float('inf')

N, S = map(int,input().split())
nums = list(map(int,input().split()))

# 연속된 부분합, S 이상 되는것. => 정렬 못함
# 모두 양수 => 포인터 두개 왼쪽부터 출발시키기.

left = 0
right = 0
total = nums[0] # [0,0] 포함으로 시작
length = INF

while True:
    if total >= S: # 목표 밸류 이상이라면,
        length = min(length,right-left+1) # 저장하고
        total -= nums[left] # 더 축소시켜보기
        left += 1 # 한칸 오른쪽으로
        if left > right:          # left 포인터가 right 포인터를 역전하는 순간
            if left == N:         # left도 끝이면 종료
                break
            right = left # right를 left까지 땡겨와줌
            total = nums[left]  # total에 left or right값을 더해줌  
    else: # 목표 밸류보다 작다면
        right += 1
        if right == N: # right 가 넘어간다면
            break
        total += nums[right] # right 더하기

print(0 if length == INF else length)

left 포인터가 right 포인터를 역전하는 순간
에 대한 분기처리를 추가적으로 작성해줘야 한다.

 if left > right:          # left 포인터가 right 포인터를 역전하는 순간
            if left == N:         # left도 끝이면 종료
                break
            right = left # right를 left까지 땡겨와줌
            total = nums[left]  # total에 left or right값을 더해줌

나에겐 이 닫힌구간으로 푸는 코드가 더 직관적으로 와닿는 듯 하다.