[백준] 1806. 부분합 - python

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

난이도: 골드4
알고리즘: 투포인터  

풀이과정

제한시간이 0.5초, 주어지는 수열의 길이 N이 100,000 이므로 이중 포문을 사용해서는 안 된다.  

  

먼저, 합이 S 이상이 되는 left와 right를 구한다. 이 때 모든 수를 더해도 S를 달성하지 못한다면 0을 출력하고 종료한다.  

  

이렇게 구해진 left와 right의 위치를 옮겨가며 부분합이 S 이상이 되면서 최소 길이를 가지는 경우를 탐색한다.  

  

부분합이 S 보다 작고 right가 수열의 맨 끝에 도달하지 않은 경우
현재 부분합에서 right에 해당하는 수를 더하고 right를 오른쪽으로 한 칸 이동  

  

그렇지 않은 경우  
현재 부분합에서 left에 해당하는 수를 빼고 left를 오른쪽으로 한 칸 이동  

  

그 다음, 현재 부분합이 S 이상이라면 최소 길이를 갱신  

  

위 과정을 left가 수열의 끝에 도달할 때까지 반복한다.  

  

소스코드

def solve():
    left = 0
    right = 0
    cur_sum = 0
    while cur_sum < s and right < n:
        cur_sum += nums[right]
        right += 1
    if cur_sum < s:  # 모두 더해도 S보다 작은 경우
        print(0)
        return

    answer = right - left  # 현재 S를 넘는 부분합의 길이
    while left < n:
        if cur_sum < s and right < n:
            cur_sum += nums[right]
            right += 1
        else:
            cur_sum -= nums[left]
            left += 1
        if cur_sum >= s:
            answer = min(answer, right - left)
    print(answer)
    return


n, s = map(int, input().split())
nums = list(map(int, input().split()))
solve()