Problem Solving/백준

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

돌돌김 2021. 2. 11. 17:59

www.acmicpc.net/problem/1806

1806번: 부분합

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

www.acmicpc.net

 

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

 

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

 

  • 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)

 

 
1 2 3 4 5 6 7 8 9 ··· 64