문제 링크
https://www.acmicpc.net/problem/1806
문제 설명
10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.
문제 풀이
처음엔 이렇게 풀었고 시간초과가 나왔다.
N,S = map(int, input().split())
numbers = list(map(int, input().split()))
sum = [0]
for n in numbers:
sum.append(sum[-1] + n)
def function():
for a in range(1, N):
for i in range(N-a+1):
if sum[i+a]-sum[i] >= S:
print(a)
return
print(0)
return
function()
나름 중복 연산 방지한다고 배열에 저장했는데... 그러다 제목의 투포인터를 떠올려 start와 end 두 개를 잡고 풀었다.
1. start, end를 1차이나게 잡는다.
2-1. 문제 조건을 만족하면 answers 배열에 저장한다.
2-2. 문제 조건을 만족하지 않으면
2-2-1. end를 먼저 1증가
2-2-2. end가 마지막에 다다랐으면 start를 증가
3. answers가 있으면 가장 작은 것을 출력하고 없으면 0 출력
코드
N,S = map(int, input().split())
numbers = list(map(int, input().split()))
sum = [0]
for n in numbers:
sum.append(sum[-1] + an)
answers = []
start = 0
end = 1
while start != N:
if sum[end] - sum[start] >= S:
answers.append(end-start)
start += 1
else:
if end != N:
end += 1
else:
start += 1
if answers:
print(min(answers))
else:
print(0)
결과
다른 사람의 코드
리뷰
'알고리즘 문제 > 백준' 카테고리의 다른 글
백준 1789번: 수들의 합 python 풀이 및 정답 코드 (0) | 2021.11.19 |
---|---|
백준 2293번: 동전 1 Python 풀이 및 정답 코드 (0) | 2021.11.14 |
백준 2252번: 줄 세우기 python 풀이 및 정답 코드 (0) | 2021.11.13 |
백준 16916번: 부분 문자열 python 풀이 및 정답 코드 (0) | 2021.11.13 |
백준 1197번: 최소 스패닝 트리 python 풀이 및 정답 코드 (0) | 2021.11.13 |