[BOJ] 13398 연속합 2 (Pyhton / 파이썬)

🧷 문제

https://www.acmicpc.net/problem/13398

n개의 정수로 이루어진 임의의 수열이 주어질 때, 연속된 몇개의 수를 선택해서 구할 수 있는 합 중 가장 큰 값을 구하는 문제이다. (단, 수열에서 수를 하나 제거할 수 있다(제거하지 않아도 된다.))

🛠 풀이

이 문제는 2차원의 DP table을 구성하여 해결할 수 있다.

Step 1.
 먼저 수열에서 수를 하나 제거했을 때 (dp[i][1])와 그렇지 않은 경우 (dp[i][0])로 나누어준다.
 dp[0][0], dp[0][1] 은 sequence[0]으로 초기화 해준다.

Step 2.
 1부터 n-1까지 for문을 돌면서
 1. dp[i][0]은 아무런 원소를 제거하지 않았을 때를 비교하면 되므로, (이전까지의 연속합 + i번째 수열)과 i번째 수열의 값을 비교해 그 중 큰값을 대입해준다.

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

 2. dp[i][1]은 수열의 특정 원소를 제거하는 경우이므로, (i번째 수열을 제거하는 경우)와 (i번째 이전에 이미 특정 원소를 제거해 i번째 수열을 선택하는 경우)로 나눌 수 있다.

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

Step 3.
 이렇게 for문을 n-1번 돌면서 res는 각 인덱스까지의 경우에서 가장 큰 값을 넣어준다.
 res를 리턴하면 우리가 원하는 답을 구할 수 있다.

느낀점

처음에 이 문제를 접했을 때는 수열에서 음수값을 따로 저장한 후에 음수값들을 하나씩 제거했을 때의 연속합을 구하는 O(N^2)의 시간복잡도를 갖는 코드를 작성했는데 당연하게도 n의 범위때문에 시간초과가 났다. DP 문제는 여러 문제들을 접하면서 어떻게 DP table을 구성할지가 중요한 것 같다. 더 많이 경험하고 더 발전해야겠다.

🖊 나의 코드

def solution(n):
    sequence = list(map(int, input().split()))

    dp = [[0] * 2 for _ in range(n)]
    dp[0][0], dp[0][1] = sequence[0], sequence[0]

    res = sequence[0]

    for i in range(1, n):
        dp[i][0] = max(dp[i-1][0] + sequence[i], sequence[i])
        dp[i][1] = max(dp[i-1][1] + sequence[i], dp[i-1][0])
        res = max(dp[i][0], dp[i][1], res)

    return res


if __name__ == "__main__":
    N = int(input())
    print(solution(N))