[백준] 부분합

출처:: www.acmicpc.net/problem/1806

분류:: 구간 합(prefix sum) , 투포인터 

 

1. 문제 이해 및 해결과정

5 10
1 2 3 4 5
# 3,4,5(12) => 3

10 10
1 1 1 1 1 1 1 1 1 10
# 10 -> 1

 

2. 풀이방법

 1. python 투포인터 

#부분합
#https://www.acmicpc.net/problem/1806
import sys
sys.stdin = open("input.txt","r")
n,m=map(int,input().split()) #n,목표
arr=list(map(int,input().split()))

s,e=0,0
sum=0
sol=1e9
tmp=0
for s in range(n):
    while e<n and sum<m:
        sum+=arr[e]
        e+=1
    if sum>=m: #부분합이 m이상일때
        tmp=e-s #길이
        sol=min(sol,tmp) #가장짧은 것의 길이 
        sum-=arr[s]
if sol==1e9:
    print(0)
else:
    print(sol)

 2. 구간합(prefix sum) , 투포인터

#부분합
#https://www.acmicpc.net/problem/1806
import sys
sys.stdin = open("input.txt","r")
n,m=map(int,input().split()) #n,목표
arr=list(map(int,input().split()))
prefix=[0] #prefixsum
tmp=0
for x in arr:
    tmp+=x
    prefix.append(tmp)

s,e=0,0
sol=1e9

while s!=n:
    if prefix[e]-prefix[s]>=m: #부분합의 차이가 m이상이라면
        sol=min(sol,e-s)
        s+=1
    else: #부분합의 차이가 m미만 이면
        if e!=n:
            e+=1
        else:
            s+=1
if sol==1e9:
    print(0)
else:
    print(sol)

 

 

3. 오답원인

 

4. 알게된 점