[백준] 1806 - 부분합

https://www.acmicpc.net/problem/1806

1806번: 부분합

문제 한줄 이해

- 수열의 부분합 중 합이 S이상인 것 중에 길이가 가장 적은 것을 구하기

생각난 풀이

문제를 읽고 생각난 필요한 조건들

1. 수열에는 10000이하의 자연수로 이루어져있다. -> 첫자리부터 더해가면 증가만 한다. -> 정렬의 효과

 

2. 부분합을 어떻게 구할것인지

-> 완전탐색을 통해 구할 수 있지만 N이 100000까지 가능하므로 시간초과 발생

-> 따라서 dp를 활용해 부분합 구하기

dp를 활용해 구하는 아이디어는 다음과 같다.

고등학교때 배운 수열을 생각해보자 이때 수열의 합을 구하기 위해 시그마를 썼었다.

이때 1~n까지의 합을 구해서 1~n-2까지의 합을 구해 빼준다면 n-1 ~ n까지의 합을 구해낼 수 있다.

 

3. 이제 두개의 포인터를 가지고 원하는 구간의 합을 계산해서 길이 구하기

dp[end] 값이 S보다 적다면 end +=1 why? 1번에서 정렬의 효과를 사용해서 작다면 포인터를 뒤로 옮겨주기

크다면 더이상 end포인터를 뒤로 갈 필요가 없다.

그래서 start포인터를 땡겨주기

import sys
n, m = map(int,sys.stdin.readline().split())
nlist = list(map(int,sys.stdin.readline().split()))
dp = [0] *(n+1)

for i in range(1,n+1):
    dp[i] = dp[i-1] + nlist[i-1]

start = 0
end = 0
result = 1e9
while start <= end:
    if end == n+1:
        break
    if dp[end] - dp[start] < m:
        end +=1
    elif dp[end] - dp[start] >= m:
        if result > end - start:
            result = end-start
        start +=1
if (result == 1e9):
    result = 0
    
print(result)