백준 13398 (연속합 2)

백준 13398 (연속합 2)

문제 링크

문제 링크 : https://www.acmicpc.net/problem/13398

문제 접근

문제 풀기 전 풀어봅시다! 위 문제의 해설을 보려면 클릭하세요.

결론부터 말하자면, 인터넷에 떠도는 풀이랑 저의 풀이는 조금 다릅니다. 연속합 문제입니다. 근데 하나의 원소를 제거한 최댓값도 고려를 해야 합니다. 난감합니다. 선택의 문제라고 할 수 있습니다. 내가 어떤 원소를 제거해야, 과연 기존의 연속합보다 더 좋을지 고민을 해야합니다. 기존의 문제에서 O(n)의 시간에 문제를 해결하는 방법에 대해 알았습니다. 그렇다면 어떤 원소를 선택해서, 거기서 또 부분합을 구해야 하는 것인가요? 이렇다면 O(n^2)의 시간이 걸리게 되어 TLE를 보게 될 것입니다.

발상을 전환해봅시다. 만약 i번째 원소를 제거하기로 마음을 먹었습니다. 그렇다면 i-1번째 원소와 i+1번째 원소가 이어지는 것입니다. 기존의 배열에서 i-1번째 원소를 포함하는 최댓값은 동적 계획법으로 해결할 수 있는데, 뒷부분이 문제입니다.

뒷부분에 대해서, i+1번째 원소에서 시작하는 최대 연속 부분합을 알 수 있다면 i-1번째 원소에서 끝나는 최대 연속 부분합과 합친다면, i번째 원소를 제거한 최대 부분합을 알 수 있는 것 아닐까요?

i번째 원소에서 시작하는 최대 연속 부분합은 사실 i번째 원소에서 끝나는 최대 연속 부분합을 구하는 과정에서 방향만 다른 것 아닌가 싶습니다. 소스 코드를 보면서 이해해봅시다.

다른 사람들의 풀이

다른 인터넷의 풀이를 봤는데, 2차원 dp 배열을 선언합니다.

dp[i][0]은 i번째 원소를 포함하고, 숫자를 제거하지 않았을 때 최대 연속 부분합.
dp[i][0]은 i번째 원소를 포함하고, 숫자를 제거했을 때 최대 연속 부분합.

위처럼 정의한 후,

dp[i][0]=max(dp[i-1][0]+arr[i], arr[i])
dp[i][1]=max(dp[i-1][1]+arr[i], dp[i-1][0])

로 점화식을 쓴다면 해결할 수 있습니다. 둘 중에 선택의 자유라고 생각합니다.

소스 코드

저는 이렇게 구현하였습니다.

import sys
n=int(input())
arr=list(map(int, sys.stdin.readline().split()))
dp=[0 for _ in range(n)]
dp_reverse=[0 for _ in range(n)]
dp[0]=arr[0]
dp_reverse[0]=arr[-1]

#숫자 제거하지 않는 경우
for i in range(1,n) : 
    dp[i]=max(dp[i-1]+arr[i],arr[i])
    dp_reverse[i]=max(arr[(n-1)-i] , dp_reverse[i-1] + arr[(n-1)-i]) 

dp_reverse.reverse() # dp_reverse는 i에서 시작하는 최대 연속 부분합입니다.
answer=max(dp)
for i in range(1,n-1) :
    answer=max(answer, dp[i-1] + dp_reverse[i+1])
print(answer)

마무리하며

i번째 원소에서 끝나는 최대 부분 연속합을 안다면, i번째 원소에서 시작하는 최대 부분 연속합도 알 수 있음을 깨닫게 하는 문제였습니다. 뭔가 발상의 전환을 하게 해준 문제라 좋습니다. 다른 분들도 풀어보시길~