[Python] 백준 1806번 문제, 부분합

<문제 링크>

 

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

1806번: 부분합

 

---

<풀이>

 

문제 해결 방법은 길이가 N인 수열에서 부분합이 S가 넘거나 같은 부분의 최소 길이를 구하는 것이다.

투 포인트로 풀면 되기 때문에 양 끝 쪽에서 시작해 부분합들을 비교해가며 right - left의 결과로 부분합의 길이를 구하면 된다.

# 1: 시작(0)부터 내(i)가 있는 곳의 부분합

# 2: 변수들 초기화, answer는 최대 1,000,000이기 때문에 1,000,001로 초기화

# 3: 투 포인트로 탐색 시작[탐색 끝날 때(left == N)까지]

# 3 if True문: 부분합(left ~ right)이 S와 같거나 넘을 경우, 최소 길이일 경우 업데이트 -> left + 1해서 최소 길이 탐색

# 3 if False문: 부분합이 S를 넘지 않아 right가 끝이 아니라면 right 먼저 증가시켜주고 그렇지 않다면 left를 증가

# 4: answer가 변하지 않았다면 부분합을 구하지 못 하기 때문에 0을 출력하고, 그렇지 않다면 answer 값을 출력

if __name__ == "__main__":
    N, S = map(int, input().split())
    arr = list(map(int, input().split()))

    # 1
    sum_arr = [0] * (N + 1)
    for i in range(1, N + 1):
        sum_arr[i] = sum_arr[i - 1] + arr[i - 1]

    # 2
    answer = 1000001
    left = 0
    right = 1

    # 3
    while left != N:
        if sum_arr[right] - sum_arr[left] >= S:
            if right - left < answer:
                answer = right - left
            left += 1
        else:
            if right != N:
                right += 1
            else:
                left += 1

    # 4
    if answer != 1000001:
        print(answer)
    else:
        print(0)