[백준] 1806 부분합 (python 파이썬)

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

1806번: 부분합

---

아이디어

1. 부분합 사용

• 부분합에 대해 간단히 얘기해보면 0 ~ N까지의 합을 미리 구해두고 합의 차((0 ~ b까지 합) - (0 ~ a까지 합))를 통해 a부터 b까지 수의 합을 빠르게 구하는 방법이다.
• 그래서 for문을 사용해서 길이가 1일 때, 2일 때... N일 때 부분합의 값을 구해보며 S값이 넘는 순간 프로그램을 종료하도록 코드를 짰다. 당연하게도 시간 초과가 떴다. 아마 길이가 긴 경우 때문인 거 같다.
• 고민 고민하다 알고리즘 분류를 보고 문제를 풀었다. 

2. 투 포인터

• 다시 보면 이해가 가지만 처음 봤을 때는 투 포인터는 생각을 못했다. 어떻게 하면 투 포인터를 떠올릴 수 있는지 잘 모르겠다. 짧은 시간제한이 힌트인 거 같긴 하다.
• 투 포인터 문제라는 것을 알면 이후 풀이 방법은 간단하다.
• 결과적으로 부분합을 사용하지 않고 투 포인터로 문제를 해결했다.

---

전체 코드

import sys
N, S = map(int, input().split())
array = [int(x) for x in sys.stdin.readline().rstrip().split()]

left = 0
right = 0
length = 100000
temp_sum = array[0]

while left <= right:
    if temp_sum >= S:
        length = min(length, right - left + 1)
        temp_sum -= array[left]
        left += 1
    else:
        right += 1
        if right < N:
            temp_sum += array[right]
        else:
            break

if length == 100000:
    print(0)
else:
    print(length)

---

코드 설명

left = 0
right = 0
length = 100000
temp_sum = array[0]

while left <= right:
    if temp_sum >= S:
        length = min(length, right - left + 1)
        temp_sum -= array[left]
        left += 1
    else:
        right += 1
        if right < N:
            temp_sum += array[right]
        else:
            break

간단하게 설명하면 부분합이 S를 넘으면 left를 한 칸 옮겨서 합을 줄여보고

아니라면 right를 한 칸 옮겨서 S를 넘는지 확인해보면 된다.

right가 N까지 가거나 left가 right를 넘기면 종료 해준다.

 

그리고 부분합이 S를 넘길 때 기존의 저장된 길이(length)와 현재 길이(right - left + 1)를 비교해서 작은 값을 저장한다.

 

출력에서 합을 만드는 게 불가능하면 0을 출력하라 하였으므로

length가 100000이면(if temp_sum >= S 구문이 실행 안된 경우) 0을 출력하고

아니라면 length값을 출력해주면 된다.