알고리즘 - Python / 백준 - 1806번 : 부분합

1806번: 부분합 (acmicpc.net)

1806번: 부분합

 

---

풀이

• 부분합과 투 포인터를 사용하는 기본적인 문제다.
• 부분합을 통해 배열의 일정 부분의 합을 쉽게 구할 수 있고 , 투 포인터를 활용해서 조건을 만족하는 구간의 길이를 찾으면 된다.
• 배열의 합이 일정 값 이상이 될 때 까지 뒤쪽 포인터를 전진시키고 해당 값이 만족되면 해당 값이 만족되지 않을 때까지 다시 앞쪽 포인터를 전진시킨다.
• 앞쪽 포인터가 전진하면서 다시 배열의 합이 일정 값 이하가 되면 다시 조건을 만족 할때까지 뒤쪽 포인터를 전진시킨다.
• 뒤쪽 포인터가 끝까지 도달하면 반복문을 종료시키고 그동안 찾은 길이중 최소값을 출력한다.

 

import sys
n , s = map(int , sys.stdin.readline().split(" "))
c = list(map(int , sys.stdin.readline().split(" ")))
d = [0 for _ in range(n+1)]
d[1] = c[0]
for i in range(2,n+1):
    d[i] = c[i-1] + d[i-1]
if d[n] < s:
    print(0)
elif d[n] == s:
    print(n)
else:
    ans , f_c , e_c = 100001 , 0 , 1
    while e_c != n+1:
        if d[e_c] - d[f_c] < s:
            e_c += 1
        else:
            ans = min(ans,(e_c-f_c))
            f_c += 1
    print(ans)

---