[백준 1806] 부분합

[백준 1806] 부분합

 

문제

10000 이하의 자연수로 이루어진 길이 n짜리 수열이 주어진다 이 수열에서 연속된 수들의 부분합 중에 그 합이 s 이상이 되는것 중 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오 

입력

첫줄에 n과 s가 주어진다.

둘째 줄 에는 수열이 주어진다.

수열의 각 원소는 공백으로 구분된다.

출력

첫 줄에 구하고자 하는 최소의 길이를 출력하며 만약 없으면 0을 출력한다.

풀이

투포인트를 이용하여 풀었다 

합 s에 이상이 되는 부분합의 개수를 카운트할 변수로 now와 그 갯수를 넣을 리스트 ans를 만들었다

일단 기본적으로 투포인트와 같은 방식으로 진행한다

 

 

while문을 이용하여 현재까지 의 합이 도 달해 야합보다 작거나 end값이 n 보다 작을 때 

sum+=data [end]하고  end 값을 +1  , now 값 또한 +1 해준다 

while문이 끝나면 그 값이 목표에 이상이면 count+1이해 준다 count는 총 몇개의 부분합이 목표값 이상으로 도달했는지 알수 있게 해준다 그리고 ans 리스트에 now값을 넣어준다 넣어주는 이유는 이 now값이 현재까지 더한 원소들의 개수를 의미한다 하며 이는 현재 우리가 구해야 하는 합이 s 이상이 되는 것의 길이를 의미한다.

그다음으로  sum-=data [0] 첫 번째 값을 빼주고 now값 또한 -1을 해준다.

위 과정을 for문을 이용하여 strat값을 증가시면서 반복해 주면 된다.

 

for루프가 끝나고 난 후 이때까지 구한 합이 s이상이 되는 부분합들의 길이를 넣은 리스트 ans를 정렬해 주면

인덱스가 0인 걸 출력해 주면 문제에서 원하는 답을 구할 수 있다.

이때 합이 없는 경우는 o을 출력해야 한다 합이 없는 경우는 count 값이 0이거나 ans 길이가 0일 때 0으로 출력해 주면 된다.

 

코드

n,s=map(int,input().split())

data=list(map(int,input().split()))

count=0
sum=0
end=0
ans=[] 
now=0

for start in range(n):

    while sum<s and end<n:
        sum+=data[end]
        now+=1
        end+=1

    if sum>=s:
        count+=1
        ans.append(now)
        
        

    sum-=data[start] 
    now-=1   

ans.sort() 
if count>0:
    print(ans[0])

    
else:
    print(0)