백준 1806번: 부분합 python 풀이 및 정답 코드

문제 링크

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

 

1806번: 부분합

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

www.acmicpc.net

 

 

문제 설명

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)

 

 

결과

 

 

 

다른 사람의 코드

 

 

 

리뷰