[ BOJ 1806 ] 부분합(Python)

문제

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

n개의 숫자 중 연속된 부분의 합이 s 이상이 되는 가장 짧은 수열의 길이를 구하면 된다.

문제 풀이

0. 입력 받기

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

1. 포인터를 옮기면서 hap 체크하기

• r이 가장 끝까지 이동하면 반복문을 멈춘다.
• hap이 s보다 작으면 nums[r]을 더해주고, r을 한칸 뒤로 이동시켜준다.
• hap이 s 이상이 되면 answer 변수에 수열의 길이를 저장해준다.
  l을 한칸 뒤로 이동시켜주기 위해 hap에 nums[l]을 빼준다.

l, r = 0, 0
answer = sys.maxsize
hap = 0

while (1):
    if hap >= s:
        answer = min(answer, r - l)
        hap -= nums[l]
        l += 1

    elif r == n:
        break

    else:
        hap += nums[r]
        r += 1

2. answer 값에 따라 출력해주기

• answer 값이 초기값과 같으면, 수열의 합이 s 이상인 수열이 없다는 뜻이다.

if answer == sys.maxsize:
    print(0)
else:
    print(answer)

코드

import sys
input = sys.stdin.readline

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

l, r = 0, 0
answer = sys.maxsize
hap = 0

while (1):
    if hap >= s:
        answer = min(answer, r - l)
        hap -= nums[l]
        l += 1

    elif r == n:
        break

    else:
        hap += nums[r]
        r += 1

if answer == sys.maxsize:
    print(0)
else:
    print(answer)