[DP] 원하는 State를 정의하여 한 칸씩 나아가는 DP / 고대 보물 지도의 비밀

문제링크

https://www.codetree.ai/missions/2/problems/secret-of-ancient-treasure-map?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

1. 핵심

• 동일한 상황에 대해서 생각
  • 특정한 위치(행)까지의 합(값)과 마이너스의 개수(열)가 동일한 경우 같은 상황이다.
• 이 문제의 포인트는 '연속'이다. 그러므로 dp의 i번째를 볼 때는 반드시 dp의 i - 1번째를 봐야하고 또 주의해야할 점은 연속을 끊어내고 내 스스로 연속의 시작점이 될 수 있다. 따라서 점화식 작성할 때 내 자신이 시작점이 될 수 있음을 인지해야한다.
• 점화식의 정의
  • DP[i][j] = i번째 숫자를 반드시 마지막으로 선택했을 때, 음수 개수가 j일 때의 최대합
  • DP[i][j] 
    • 마지막으로 선택한 i번째 숫자가 양수인 경우 - j 에 변화는 없다. dp[i][j] = max(dp[i][j], nums[i], dp[i-1][j] + nums[i])로 나타낼 수 있다.
    • 마지막으로 선택한 i번쌔 숫자가 음수인 경우 - 음수의 개수가 j개 되기 위해서는 j - 1에서 + 1을 해야 j가 된다. 따라서 점화식은 dp[i][j] = max(dp[i][j], dp[i][j - 1], nums[i])라고 할 수 있다.

2. 코드(Python)

n, k = map(int, input().split())
nums = [0] + list(map(int, input().split()))

# 2차원dp 음수의 개수를 기록
# dp[i][j]: i번째 숫자를 반드시 선택했을 때 음수의 개수는 j이다. 값은 i번째 숫자를 선택햇을 때까지의 합
# 현재 인덱스까지의 합과 음수의 수가 일치하면 같은 상황!!
# 연속하게 가지고 오려면 반드시 dp[i - 1]에만 가져와야함...
# dp[i - 2] 연속불가!!

inf = int(1e9)
dp = [[-inf for _ in range(k + 1)] for _ in range(n + 1)]

dp[0][0] = 0
for i in range(1, n + 1):
    for j in range(k + 1):
        if nums[i] >= 0:
            # 연속을 끊고 내 자신만을 선택할 수 있어야함!
            dp[i][j] = max(dp[i][j], dp[i - 1][j] + nums[i], nums[i])
        else:
            if j - 1 >= 0:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + nums[i], nums[i])
            
ans = 0
for row in dp:
    ans = max(ans, max(row))

print(ans)