연속합 2 ( 13398 번 )

13398번: 연속합 2

 

---

🧠 알고리즘

• 동적 계획법 (DP, Dynamic Programming)

 

✔️ 동작 방식

문제 핵심 아이디어

• n개의 수열에서 한 번 숫자를 제거할 수 있는 상태를 포함하여 연속된 부분합의 최댓값을 구하는 문제.
• 2차원 DP를 사용:
  • dp[0][i] → 숫자를 제거하지 않고 i번째까지의 최대 연속합
  • dp[1][i] → 한 번 숫자를 제거할 수 있는 상태에서 i번째까지의 최대 연속합

주요 로직 요약

[ 초기화 ]

dp[0][0] = dp[1][0] = n_list[0]
>> 0번째 숫자까지의 최대합은 제거 여부와 상관없이 첫 숫자 값으로 시작.

 

[ DP 점화식 ]

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

1. dp[0][i] → i번째 숫자를 새로 시작할지, 이어서 합칠지 결정
2. dp[1][i] → 이미 제거를 사용했거나, i번째 숫자를 제거하여 최대합을 갱신

 

[ 결과 반환 ]

return max(max(dp[0]), max(dp[1]))

---

 

🧾 코드

import sys

def _main(n, n_list):
    """
        dp 문제 : 메모리제이션
        이차형 dp 문제
        dp[0] >> 숫자 를 제거 않고 최댓값
        dp[1] >> 숫자 를 제거할수 있는 경우 최댓값
    """
    dp = [[-1001] * n for _ in range(2)]
    dp[0][0] = dp[1][0] = n_list[0]

    for idx in range(1, n):
        dp[0][idx] = max(n_list[idx], dp[0][idx - 1] + n_list[idx])
        dp[1][idx] = max(dp[1][idx - 1] + n_list[idx], dp[0][idx - 1])
        
    return max(max(dp[0]), max(dp[1]))

 
n = int(sys.stdin.readline().rstrip())
n_list = tuple(map(int, sys.stdin.readline().rstrip().split()))

print(_main(n, n_list))

---

 

⏱️ 시간 복잡도

for idx in range(1, n) : 연속된 숫자를 순회하며 메모리제이션을 채워나감 ( 선형 시간 )

해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )