📚 1806 - 부분합

부분합

이해

수들의 합 2 과 유사한 문제이다.
처음 보았을 때는 dfs로 풀면 되는 줄 알았지만 런타임 에러가 발생하여 당황했다.
그럼에 조건을 알아보던 중, 답을 찾는데 시간을 많이 투자한 것 같다.

✔️ 이와 같은 문제에서 가장 좋은 방법
시작 값을 어떻게 줘야할까?

• start : 0, end : 0 으로 준다.
• result = arr[0] : 현재까지 계산 결과 저장한 변수는 배열의 0번째 인덱스부터 저장한다.

언제 start, end를 증가시킬까?

• 만약, start에서 end까지 합을 저장한 result가 기준 값보다 크거나 같을 경우, start를 증가시켜야 한다.
• 만약, start에서 end까지 합을 저장한 result가 기준 값보다 작을 경우, 다음 차례로 넘어가기 위해 end += 1을 하고 result += arr[end]를 한다.

소스

import sys

read = sys.stdin.readline

n, s = map(int, read().split())

arr = list(map(int, read().split()))

start = 0
end = 0
permission = arr[0]

result = 100001


while True:

    if permission >= s:
        permission -= arr[start]
        result = min(result, end - start+1)
        start += 1
    else:
        end += 1
        if end == n:
            break
        permission += arr[end]


if result == 100001:
    print(0)
else:
    print(result)

이 문제에서 런타임에러, 메모리에러 등 여러가지 에러를 만나게 되었다.
잘 풀리지 않는다면 구글링을 하자!

참고 : https://hbj0209.tistory.com/143