https://www.acmicpc.net/problem/1806
1806번: 부분합
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
www.acmicpc.net
코드
from itertools import accumulate
from collections import deque
input = __import__('sys').stdin.readline
n, s = map(int, input().split())
li = list(accumulate(list(map(int, input().split()))))
li = deque(li)
li.appendleft(0)
mn = float('inf')
l, r = 0, 1
while r <= n:
if li[r] - li[l] >= s and l < r:
mn = min(mn, r - l)
l += 1
else:
r += 1
if mn == float('inf'): print(0)
else: print(mn)
풀이
주어진 수열의 부분합이 특정값이 넘을 때, 그중 가장 길이가 짧은 것의 길이를 찾으면 된다.
우선, 주어진 시간의 길이가 짧기 때문에 빠른 입력을 사용해준다.
그리고 나서 파이썬 자체에서 지원하는 누적합 라이브러리를 사용하면 코드의 길이를 줄일 수가 있다.
가장 짧은 길이의 누적합을 탐색하기 위해서는 투포인터 알고리즘을 활용하면 된다.
투포인터 알고리즘을 활용하기 위해서 deque 라이브러리를 불러와주고 최저값을 저장하는 mn 변수에 inf를 저장하여
최종값이 inf일 경우 0을 출력하고 그렇지 않을 경우 최소값을 그대로 출력해주면 된다.
'Koala - 9기 > 코딩테스트 준비 스터디' 카테고리의 다른 글
[백준 / Python] 15038번 Lounge Lizards (0) | 2023.01.25 |
---|---|
[백준/c++] 3027번 입국심사 (Binary Search) (0) | 2023.01.25 |
[백준/Java] 11722번 가장 긴 감소하는 부분 수열 (0) | 2023.01.22 |
[python] 13732 - Falling apples (0) | 2023.01.22 |
[백준/c++] 16236번 아기상어 (0) | 2023.01.20 |