[코테] 백준 브루트 포스 1806번 문제

1806번 : 부분합

문제 링크

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

문제 설명

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

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

문제풀이

투포인터 기법을 이용해서 아래의 2개 경우를 구현하면 된다.

1. 부분배열의 합이 S보다 작으면 end를 1뒤로 옮기고 해당 포인트의 수를 더한값을 저장
2. S이상이면 길이를 저장하고 start를 1뒤로 옮긴다.

import sys
input = sys.stdin.readline

N, S = map(int, input().split())
arr = list(map(int, input().split()))

start, end = 0, 0
tempSum = arr[0]
result = 100001

while start <= end : 
    if tempSum >= S :
        result = min(result, end-start+1)
        tempSum -= arr[start]
        start += 1
    else : 
        end += 1
        if end < N : 
            tempSum += arr[end]
        else : 
            break

if result == 100001 : 
    print(0)
else : 
    print(result)