[Python] 백준 #1806- 부분합[try_again]

문제

---

1806번: 부분합

코드

---

My answer(시간초과)

import sys
input=sys.stdin.readline

n,s=map(int,input().split())
num=list(map(int,input().split()))
dp=[0 for _ in range(n)]
answer=0

for i in range(len(num)):
    if(num[i]>=s):
        answer=i+1

for i in range(n):
    for j in range(n-i):
        dp[j]=dp[j]+num[j+i]
        if(dp[j]>=s):
            answer=i+1
            break
    if(answer!=0):
        break
    for j in range(n-i,n,1):
        dp[j]=0  
print(answer)

import sys
input=sys.stdin.readline

n,s=map(int,input().split())
num=list(map(int,input().split()))
answer=0

for i in range(n):
    dp=[]
    dp=list(sum(num[j:j+i+1]) for j in range(len(num)-i))
    for k in dp:
        if(k>=s):
            answer=i+1
            break
    if(answer!=0):
        break   
print(answer)

Another answer

import sys

N, S = map(int, input().split())
arr = list(map(int, input().split()))

left, right = 0, 0
tmp_sum = 0
min_length = sys.maxsize

while True:
   if tmp_sum >= S:
       min_length = min(min_length, right - left)
       tmp_sum -= arr[left]
       left += 1

   elif right == N:
       break

   else:
       tmp_sum += arr[right]
       right += 1

if min_length == sys.maxsize:
   print(0)
else:
   print(min_length)

풀이

---

우선 나는 그냥 브루트포스로 문제를 풀어보려고 했다. 우선 두번째 코드로 풀었었는데, 시간초과가 떠서 슬라이싱,sum함수, 많은 메모리 사용 때문인 것 같아서 첫번째 코드로 수정했다. 배열을 여러개 만들지 않고 sum함수도 뺏고 슬라이싱도 빼서 되줄알았는데 그냥 이 문제가 시간제한이 빡센 문제였다. 특정 알고리즘으로만 풀 수 있는 문제였다.. 이 문제는 투포인터라는 알고리즘을 사용한다고 한다. 

시작점과 끝점을 적절히 바꾸면서 그 사이에 있는 부분들의 합 구하는 것이다. 처음은 시작점, 끝점을 0으로 설정하고

시작점과 끝점을 움직이면서 구간의 길이를 조절하게 되는데, 현재 부분합이 S보다 작다면, 숫자가 더 있어야 하므로 구간을 더 늘리기위해 끝점을 늘려주고 현재 부분합이 S보다 크다면, 숫자를 줄여야 하므로 시작점을 뒤로 움직여 구간을 줄여준다. 이번 기회에 투포인터 알고리즘도 공부해놔야겠다.