1806 - 부분합

info

• 문제 보기: 1806 - 부분합
• 소요 시간: 10분 28초
• 풀이 언어: python
• 체감 난이도: 2️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

투포인터

풀이 코드

info

• 메모리: 42168 KB
• 시간: 72 ms

import sys
input = sys.stdin.readline

def solution():
    n, s = map(int, input().split())
    series = list(map(int, input().split()))
    
    l, r = 0, 0
    sum = 0
    ans = 1e6
    
    while True:
        if sum >= s: # 합 조건 충족 -> 길이값 갱신 시도
            ans = min(ans, r-l)
            sum -= series[l]
            l += 1
        elif r >= n: # 끝 도달 -> 종료
            break
        else: # 원소 추가
            sum += series[r]
            r += 1
            
    if ans == 1e6:
        print(0)
    else:
        print(ans)


if __name__ == '__main__':
    solution()

풀이 해설

수열의 연속된 부분을 찾아야 하는 문제이므로, 연속된 구간의 양 끝 인덱스를 l과 r로 나누어 최적화할 수 있다.

( 단, 수열 인덱스의 범위는 $[\:l,\:r\:)$ )

1️⃣ 부분합이 S 이상일 때

if sum >= s: # 합 조건 충족 -> 길이값 갱신 시도
    ans = min(ans, r-l)
    sum -= series[l]
    l += 1

부분합 조건은 충족하므로 현재의 길이가 정답의 후보가 될 수 있다.

따라서 ans와 비교하고, l 인덱스를 한칸 옮겨 부분합 값을 줄여본다.

(줄어든 부분합 값은 다음 iteration에서 평가)

2️⃣ 부분합이 S 미만 + r이 수열 범위를 벗어남

elif r >= n: # 끝 도달 -> 종료
    break

부분합 조건을 만족 못하므로, 값을 늘려야 하는 case이다.

하지만 l은 옮겨봤자 부분합 값이 늘어날 수 없고,

r은 더이상 옮길 수 없으므로 명백한 루프 탈출 조건이 된다.

3️⃣ 부분합이 S 미만 + r이 수열 범위 이내

else: # 원소 추가
    sum += series[r]
    r += 1

부분합 조건을 만족 못하므로, 값을 늘려야 하는 case이다.

r을 옮길 수 있으므로 한 칸 옮겨 부분합 값을 늘린다.