[백준 1806번] 파이썬 - 부분합

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

 

 

# 조건

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

 

입력

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

 

출력

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

 

# 접근 방법

• 내림차순으로 정렬하여 풀려했는데 수열이기 때문에 따로 정렬해주면 안된다.
• 따라서, 누적 합 문제이며 두 포인터를 사용하면 된다.
• 합이 기준 값을 넘을 때, 그 길이를 더해주고,
• 크다면 left pointer 이동
• 작다면 right pointer 이동

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
  
N, M = map(int, input().split())  
nums = [*map(int, input().split())]  
  
l_pointer = 0  
r_pointer = 0  
result = float('INF')  
part_sum = nums[0]  
while r_pointer < len(nums):  
    if part_sum >= M:  
        result = min(result, r_pointer - l_pointer + 1)  
        part_sum -= nums[l_pointer]  
        l_pointer += 1  
  
    else:  
        r_pointer += 1  
        if r_pointer < len(nums):  
            part_sum += nums[r_pointer]  
  
print(result if not result == float('INF') else 0)