[BOJ] 1806 부분합 - python

1806번: 부분합

1806번: 부분합

풀이

처음에는 0항부터 현재 항까지의 부분합을 구해놓은 후 이 차이를 이용하여 시간초과를 해결하려 하였다. 근데 그렇게 해도 될 것 같긴한데 어쨌든간에 최악의 경우 O(N*N) 시간이 걸린다는 점을 간과했다. 투포인터를 사용하여, start를 증가시키면서 한 번이라도 end가 N-1까지 간다면 S를 만들 수 없다는 점을 이용하자 start와 end를 증가시키며 진행하고, '연속된 수들의 합' 을 이용하는 것이므로 양 끝 값을 더하고 빼는 방법으로 모든 합을 계산하지 않게 시간초과를 피한다. start,end를 0으로 설정한 후 cum_sum = su[0] 으로 초기화한다. cum_sum이 S이상이라면 → 해당 start에서는 최소 길이를 더 이상 구할 수 없으므로 answer min을 갱신하고 start를 +1 한다. cum_sum에서 이전 su[start]값은 빼준다. cum_sum이 S미만이라면 → end를 증가시켜 다음 cum_sum = su[end]값을 갱신한다. 이때 만약 end가 끝까지 갔다면, (마지막 N-1까지 보긴 해야하므로 증가시킨 후 end가 N인 경우를 끝으로 한다.)아무리 start를 증가시켜도 S이상이 나올 수 없으므로 반복문을 나온다. answer가 무한대라면 한 번도 갱신되지 않은 것이므로 0을 출력하고 , 그렇지 않으면 min값 answer를 출력한다.

시간초과 코드 

import sys
def input():
    return sys.stdin.readline().rstrip()

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

answer = float('inf')
#연속된 수들의 부분합 중에 합이 S이상이 되는 것 중, 가장 짧은 길이
#일단 0부터 각 i까지의 합을 구해놓기
dp = [0 for _ in range(N)]
dp[0] = su[0]

for i in range(1,N):
    dp[i] = dp[i-1] + su[i]
    if dp[i] >= S:
        answer = i + 1

#합 생성 불가
if dp[-1] < S:
    print(0)
    exit()

#각 자리부터 돌면서 연속된 거 중에 S보다 큰거 찾기
for i in range(1,N):
    for k in range(i+1,N):
        target = dp[k] - dp[i-1]
        if target >= S:
            answer = min(answer,k-i+1)
            break

print(answer)

최종 코드

import sys
def input():
    return sys.stdin.readline().rstrip()

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

#투 포인터 사용
#start,end를 0부터 시작하도록 한다.
#0부터 N-1까지 start를 증가시키면서 연속된 수의 합을 구할 건데, '연속된 수들의 합'이므로 양 끝 포인터들을 더하고 빼면서 시간 초과를 피할 수 있다.
#한 start에서 end가 끝까지(N-1)까지 갔다면 그 다음 start에서는 절대 S이상을 낼 수 없다.

answer = float('inf')
cum_sum = su[0] #0항의 값은 미리 더하고 시작해야 한다.
start,end = 0,0
while start < N:
    if cum_sum >= S: #S이상일 때
        answer = min(answer, end - start + 1)
        cum_sum -= su[start]
        start += 1
    else: #합이 S이하일 때
        end += 1
        if end == N: #end가 끝까지 왔으면
            break
        cum_sum += su[end]

if answer == float('inf'):
    print(0)
else:
    print(answer)

얻어가는 것

• 투포인터

  #투 포인터 start, end설정
  start,end = 0
  
  while start < N: #종료조건
  	if function(start,end) >= S:
  			#어쩌구저쩌구
  			start += 1 #start조절
  	else:
  			end += 1 #end조절
  			if end == N:
  					break
  

• → '연속된 값' 에서 양 끝 값을 건드려서 **특정 조건 (ex. cum_sum)**값을 구할 수 있을 때 사용할 수 있다.

느낀점

"211124"

소요 시간 : 3h이상

• 조건을 잘 살피고, '연속된 값들 중' 양 끝 값을 건드려서 특정 조건을 만족시킬 수 있다면 투 포인터를 생각해보자.
• 시간 초과 정말 힘들다
• 그리고 edge들 조건 설정이 매우 헷갈리는데 예시를 통해 잘 생각해보자