백준 #31929 너 재능 있어

문제 링크

[31929 너 재능 있어]

문제 설명

$N$번의 승리를 할 수 있고 $M$번의 패배를 할 수 있는 게임이 있을 때 $N + M$번 게임을 하면서 얻을 수 있는 최대 점수를 구하는 문제

코드

import sys
input = sys.stdin.readline


N = int(input())
W = [0] + list(map(int, input().split()))
M = int(input())
L = [0] + list(map(int, input().split()))
K = int(input())
dp = [[0] * (M + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    dp[i][0] = dp[i - 1][0] + W[i]
for j in range(1, M + 1):
    if dp[0][j - 1] % K == 0:
        dp[0][j] = dp[0][j - 1] - L[j]
    else:
        dp[0][j] = dp[0][j - 1] - min(dp[0][j - 1] % K, L[j])
for i in range(1, N + 1):
    for j in range(1, M + 1):
        if dp[i][j - 1] % K == 0:
            dp[i][j] = max(dp[i - 1][j] + W[i], dp[i][j - 1] - L[j])
        else:
            dp[i][j] = max(dp[i - 1][j] + W[i], dp[i][j - 1] - min(dp[i][j - 1] % K, L[j]))

print(dp[-1][-1])

풀이

현재 점수가 이전 점수에 따라 영향을 받는 것을 보고 바로 DP로 풀어야겠다고 생각했다. $dp[i][j]$를 $i$번 승리하고 $j$번 패배했을때 최대 점수로 정의하고 문제 조건 그대로 식을 세워줬다. 초기에 승리만했을경우, 그리고 패배만 했을 경우는 점수를 미리 배열에 넣어주었다.