❓1912번 : 연속합
〽️ 문제 요약
n개의 정수로 이루어진 임의의 수열이 주어질 때, 연속된 한 개 이상의 수를 선택할 때 구할 수 있는 합 중 가장 큰 합을 구하면 되는 문제
🤨 접근법
가장 먼저 생각할 수 있는 방법은 연속된 N(1, … , n)개의 수를 선택하는 모든 경우의 수를 구해서 가장 큰 sum을 구하기이다. 이 경우 O(n^2)의 시간복잡도를 가진다.
아무래도 시간 제한에 걸릴 것 같으므로 문제 유형으로 소개된 DP 방식으로 풀이해보도록 하자.
가장 머리가 아팠던 부분은 i번째 수를 부분 합에 포함시키지 않았을 때 수가 당장 크더라도 이전 수들과 연속해서 합쳐진다면 더 클 수도 있지 않을까? 이 점을 고려하는 것이다.
예를 들어 1 100 2 -5 3 수열이 있을 때 연속되는 합을 구하는 과정에서 -5가 나왔다고 건너 뛰게 되면 이전에 등장한 100이라는 수를 포함시키지 못하게 되므로 최대 연속합을 구하지 못하게 된다.
이를 DP의 Tabulation을 활용해서 고려할 수 있다.
우리는 단 하나를 선택하더라도 꼭 숫자를 연속해서 선택해야 한다. 그렇기 때문에 부분 연속합을 구할 때 i번째 수를 고려하는 방법은 이전 까지의 부분합과 i 번째 수를 합칠지, 아니면 i번째 수부터 다시 부분 연속합을 구해낼지 두 가지 선택지 밖에 존재하지 않는다.
예를 들어, 예제 [10, -4, 3, 1, 5, 6, -35, 12, 21, -1] 에서 첫 번째 수인 10을 부분 연속합에 포함시키고 -4를 고려할 때, -4를 10과 더해 연속 부분 합으로 가져갈지, 아니면 -4부터 다시 시작할지 선택하면 된다. 그 판단은 두 선택지 중 더 큰 경우를 선택하면 될 것이다. 이를 다음과 같이 코드로 나타낼 수 있다.
numList[i] = max(numList[i], numList[i-1]+numList[i])수열의 첫 번째 수부터 Tabulation을 진행한다면 이전 인덱스와 이어서 연속합이 되던, 다시 처음부터 연속 합을 시작 하던 어쨌든 연속된 수의 합이 되므로 조건에 성립하게 될 것이다. 만약 중간부터 Tabulation을 진행하면 그 이전에는 어떤 방식으로 최대 연속합이 구해졌는지 알 수 없으므로 논리적으로 정답이라고 판단할 수 없다.
🔡 코드
import sys
input = sys.stdin.readline
n = int(input())
numList = list(map(int, input().rstrip().split()))
for i in range(1, n):
numList[i] = max(numList[i], numList[i-1]+numList[i])
print(max(numList))별도의 Tabulation을 위한 리스트를 만들지 않고, 입력받은 수열에서 인덱스를 업데이트 하는 방법으로 Tabulation을 진행하는 코드이다.
📚 고찰
풀이를 참고하기 이전에 생각할 수 있었던 풀이였지만 접근법에서 기술했던 부분인 중간부터 Tabulation을 진행하면 이전의 최대 연속합이 계속 연속해서 구해졌는지, 어떻게 구해졌는지 알 수 없어서 이렇게 접근하면 안될 것 같다고 생각했다. 하지만 처음의 수부터 Tabulation을 진행하게 되므로 논리적으로 성립한다는 걸 알 수 있었다.
DP 너 이샛키 언젠간 내가 1트 솔로 혼내주겠어
