[BOJ 백준] 1806번 : 부분 합(Python, 파이썬)

www.acmicpc.net/problem/1806

1806번: 부분합

 

문제의 이름에서도 알 수 있듯 부분합을 활용하는 문제이다.

 

부분합이란 시작점과 끝점을 정해서 해당 구간 내에 있는 원소들의 합을 구하는 것이다.

 

• for i in range(1, n+1):
      prefix[i] = prefix[i-1] + _list[i-1]

 

이 문제는 굳이 부분 합을 사용하지 않고, 투 포인터로도 풀 수 있는 문제였다. 

 

투 포인터 소스코드

import sys

n,s = map(int, input().split())
_list = list(map(int, input().split()))

start, end, cur = 0, 0, 0
answer = 1000001

while True:    
    if cur >= s:
        answer = min(answer, end - start)
        cur -= _list[start]
        start += 1
    elif end == n:
        break
    else:
        cur += _list[end]
        end += 1
if answer == 1000001:
    answer = 0        
print(answer)

 

 

부분 합 소스코드

import sys

n,s = map(int, input().split())
_list = list(map(int, input().split()))
prefix = [0]*(n+1)
start, end = 0, 1

for i in range(1, n+1):
    prefix[i] = prefix[i-1] + _list[i-1]

answer = 1000001
while start < n:
    if prefix[end] - prefix[start] >= s:
        answer = min(answer, end-start)        
        start += 1
    else:
        if end < n:
            end += 1
        else:
            start += 1
   
if answer == 1000001:
    answer = 0        
print(answer)