풀이_1806.md

🪝 백준 1806번 (부분합)

• Date : 2021.03.23(일)
• Time : 20분

문제

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

입력

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

출력

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

풀이

while start < n:

    if answer >= s:
        mini = min(mini, cnt)

    if answer >= s or end == n - 1:
        answer -= num[start]
        start += 1
        cnt -= 1

    else:
        end += 1
        answer += num[end]
        cnt += 1

: answer이 원하는 값보다 크거나 마지막인덱스 전까지 왔을 때는 start 지점을 다시 설정해줘야한다. 만약 그렇지 않다면 (answer이 원하는 값보다 아직 작거나 마지막 인덱스 전까지 남았을 때) 마지막 인덱스를 늘려주고 값을 더해나간다. 만약 answer이 s보다 크거나 갔을 때는 이미 구해져있는 최소카운트와 현재 최소카운트 더 작은 것을 최소값을 두고 계속 진행해야한다. 그 이유는 더 작은 카운트가 나올 수 있기 때문이다.