파이썬 알고리즘 298번 | [백준 1806번 & 2003번] 부분합 / 수들의 합 - 투포인터

298 부분합

1) 어떤 전략(알고리즘)으로 해결?

• 투포인터

2) 코딩 설명

<내 풀이>

• start, end 는 둘다 처음에 0을 가리키도록 설정합니다.
• 현재 start,end 를 통해 나온 부분합이 조건에 맞는 아이인 지 확인하고 부합하지 않다면 포인터를 옮겨줍니다.

import sys

N,S = map(int,sys.stdin.readline().rstrip().split())
lis = list(map(int,sys.stdin.readline().rstrip().split()))

# 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이

answer = int(1e9) # 가장 짧은 구간의 길이 (S랑 같거나, 보다 큰 애 찾으면 갱신 체크)
st, en = 0,0 # start pointer, end pointer
#total_sum = 0 
# 부분합 초기값 : 리스트의 맨 처음 값으로 해야 함
# 안그러면 list[0:0] 이 목표값보다 작아서 list[0:1] 검사 위해
# end 포인터를 1로 옮기면서 부분합에 옮긴 부분(list[1])의 합을 더해줘야 함
# 이때 부분합에는 맨 처음 값이 있어야 정상적으로 부분합이 더해짐
# 0으로 해놓으면 list[0:1] 값이 아닌 list[1:1] 값이 부분합이 되니깐..

total_sum = lis[0] # 부분합 , S랑 크기 비교해줄 것 

while en<N  : # 작으면 끝 포인터 증가, 크면 시작 포인터 증가하는게 투포인터의 기본 
    # print(st, en, total_sum, en-st+1)
    if total_sum >= S :
        answer = min(answer, en-st+1)
        total_sum-=lis[st]
        st+=1
        
    else : 
        en+=1
        if en==N: break  
        # en 이 lis 범위 벗어나나 체크 / lis  뒤에 여분 칸 하나 더 만들어도 좋을 듯 
        total_sum+=lis[en]

if answer==int(1e9) : print(0)
else : print(answer)

<다른 분의 풀이 or 내 틀렸던 풀이, 문제점>

1) 처음에 부분합은 dp 로 푸는 줄 알았습니다

• 그래서 dp로 부분합을 어떻게든 구현해보려다가 한계가 있음을 깨닫고 문제 분류를 참조해 투포인터임을 파악했습니다.

2) 시간초과 & 인덱스 에러

• 시간초과 : 구간마다의 합을 sum(lis[st:en]) 와 같은 형식으로 지정해서 매번 연산을 수행해주었기 때문입니다.
  • 투포인터에서는 누적합(내가 현재까지 찾은 합/값)을 한 변수를 지정해 사용하면서 start pointer를 오른쪽으로 옮기면 start pointer 의 이전 위치에 있던 값을 변수에서 빼주고, end pointer를 오른쪽으로 옮기면 end pointer에 있는 값을 변수에 더해주는 방식으로 구간의 합을 구해준다고 합니다.
• 아직 내가 찾고자 하는 값이 더 작으면 end pointer을 오른쪽으로 옮겨야 합니다. 이때 end pointer을 오른쪽으로 옮기고 새롭게 추가되는 값을 누적합 변수에 더해줘야 하는데 옮긴 end pointer 값이 리스트 범위를 벗어나는 것에 대한 예외처리가 필요했습니다.
• 혹은 예외처리 대신 리스트 맨뒤에 하나의 [0]을 추가헤주는 방법도 있습니다. (그럼 다음 while문에서 end<N 에 의해 걸러지게 됩니다. 근데 저는 예외처리로 해주었습니다.

import sys

N,S = map(int,sys.stdin.readline().rstrip().split())
lis = list(map(int,sys.stdin.readline().rstrip().split()))

# 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이

answer = int(1e9) # 가장 짧은 구간의 길이
st, en = 0,1 # start pointer, end pointer

while en<N : 
    # print(st,en,sum(lis[st:en]), answer)
    if sum(lis[st:en]) >= S :
        answer = min(answer, en-st)
        st+=1
    else : 
        en+=1

print(answer)

<반성 점>

• 처음에 부분합 누적의 초기값을 잘못 설정했었습니다.
• 제가 짠 코드의 특성에 의해서 초기값은 맨 처음 변수로 해주었어야 하는데 제가 생각없이 0으로 초기화하였기 때문입니다.

<배운 점>

• 투포인터 개념을 복습했습니다.
  https://www.youtube.com/watch?v=ttLRltNDiCo
  

• 제가 구현한 방법말고도 구현 방법이 다양하다고 합니다.

• 저는 while 문으로 처리했지만 start를 for i in range(N) 만큼 돌면서 풀이하는 방법도 존재합니다.

  • 각 경우마다 start를 고정시켜두고 while을 통해 end만을 늘리며 내가 찾는 값이 나오면 그때 작업을 한 뒤 넘어가는 방식입니다.

# n = 데이터의 개수, m = 구하고자 하는 부분 연속 수열의 합
n, m = 10, 6
data = [8, 4, 6, 2, 1, 10, 6, 2, 2, 4]

count = 0
partial_sum = 0
end = 0

for start in range(n):
    # end값을 가능한 만큼 증가시킨 다음
    while partial_sum < m and end < n:
        partial_sum += data[end]
        end += 1
    
    # 부분 합이 m이라면 카운트를 증가시킨다.
    if partial_sum == m:
        count += 1
    # start값을 1 증가시키기 전에 해당 수열의 값을 빼준다.
    partial_sum -= data[start]

print(count)

• 이 for 문 방식이 좀 더 헷갈리지 않고 구현할 수 있는 방식이라고 생각해 바로 적용해보고자 2003번 문제를 추가적으로 풀었습니다.
• 이 문제는 구간의 부분합들 중 M이 되는 것들의 갯수를 찾는 문제였습니다.
• 따라서 포인터들을 움직여주다가 M이 되는 경우엔 ANSWER 을 증가시켜주며 문제를 해결했습니다.

import sys
# https://www.acmicpc.net/problem/2003
N,M = map(int,sys.stdin.readline().rstrip().split())
lis = list(map(int,sys.stdin.readline().rstrip().split())) + [0]

start,end = 0,0
total_sum = lis[0]
answer = 0

for i in range(N) : # st pointer
    while end<N and total_sum<M:
        end+=1
        total_sum+=lis[end]
    if total_sum==M :
        answer+=1
    total_sum-=lis[start]
    start+=1
print(answer)