[ BOJ 1806 ] 부분합(Python)

uoayop·2021년 6월 1일
0

알고리즘 문제

목록 보기
79/103
post-thumbnail

문제

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

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


문제 풀이

0. 입력 받기

n, s = map(int,input().rsplit())
nums = list(map(int,input().rsplit()))
  1. 포인터를 옮기면서 hap 체크하기
  • r이 가장 끝까지 이동하면 반복문을 멈춘다.
  • haps보다 작으면 nums[r]을 더해주고, r을 한칸 뒤로 이동시켜준다.
  • haps 이상이 되면 answer 변수에 수열의 길이를 저장해준다.
    l을 한칸 뒤로 이동시켜주기 위해 hapnums[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
  1. 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)
profile
slow and steady wins the race 🐢

0개의 댓글