Baekjoon 백준 알고리즘 - 부분합( 1806 )

1. 문제 소개

• prefix sum 과 투포인터 문제다.

2. 코드

import sys
input = sys.stdin.readline


def solution():
    input_str = input().split(" ")
    n, s = int(input_str[0]), int(input_str[1])
    input_str = input().split(" ")
    arr = [int(x) for x in input_str]
    prefix_sum = [0] * (n+1)

    # set two pointer
    sp = 0
    ep = 1
    min_cnt = n

    # set prefix_sum
    while(ep <= n):
        prefix_sum[ep] = prefix_sum[ep-1] + arr[ep-1]
        ep += 1

    ep = 0

    if prefix_sum[-1] < s:
        min_cnt = 0
    else:
        while(sp <= ep and ep <= n):
            if (prefix_sum[ep] - prefix_sum[sp]) >= s:
                if min_cnt > (ep-sp):
                    min_cnt = (ep-sp)
                sp += 1
            else:
                ep += 1

    print(min_cnt)


if __name__ == '__main__':
    solution()

3.코멘트

• 문제에 부분합의 충족조건을 만족하지 않는 경우 0 을 출력하는 조건을 놓쳐 시간을 꽤 썼다.
• 문제를 대충 읽지 말자..