링크 : https://www.acmicpc.net/problem/1806
문제 설명
10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.
제한조건
시간제한 : 0.5초
코드
import sys
input = sys.stdin.readline
N, S = map(int, input().split())
sequence = list(map(int, input().split()))
front = 0
rear = 0
sumAll = 0
line = N+1
while(front < N):
if sumAll >= S:
line = line if line < rear-front else rear-front
sumAll = sumAll - sequence[front]
front = front + 1
elif rear >= N:
sumAll = sumAll - sequence[front]
front = front + 1
else:
sumAll = sumAll + sequence[rear]
rear = rear + 1
if line > N:
print(0)
else:
print(line)
아이디어
1. 연속된 수들의 부분합 중 S 이상인 것 부분합의 최소 길이를 찾는 문제니 배열 앞에서부터 투포인터 방식으로 순차적으로 부분합을 확인하며 S보다 크면 길이를 체크한다.
투포인터 알고리즘을 본 적이 있으면 바로 떠오르게 해줄만한 연습문제였는데 다른 문제도 이렇게 뭐를 써야할지 바로바로 떠올랐으면... 그리고 좀 대충 찍어내듯 쓰지 말고 정리해서 쓰자...
*문제가 중간에 계속 틀렸었는데 이유가 가능한 경우가 없으면 0을 출력하라 말했는데 그걸 안봐서... 문제를 좀 천천히 봐야하는데 생각을 실천하도록 노력하자..
'알고리즘' 카테고리의 다른 글
백준 - 2064 IP주소 (0) | 2023.01.27 |
---|---|
프로그래머스 - 정수 삼각형 (0) | 2023.01.26 |
백준 - RGB거리 (0) | 2022.12.20 |
프로그래머스 - 혼자 놀기의 달인 (0) | 2022.12.20 |
프로그래머스 - 모두 0으로 만들기 (0) | 2022.12.19 |