[백준] 31929 - 너 재능 있어

문제 링크

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

문제 요약

민석이는 앞으로 총 N번의 승리와 M번의 패배를 경험하게 됩니다. 각 승리와 패배는 각각 다른 점수를 주거나 빼앗습니다.

• 승리 시 iii번째 승리에서 Wi만큼의 점수를 얻습니다.
• 패배 시 jjj번째 패배에서 Lj​만큼의 점수를 잃습니다.

점수 보호 메커니즘이 존재합니다. 점수는 K점마다 보호 구간이 있으며, 현재 점수가 a×K+b(0<b<K)인 상태에서 패배하면 최대 b점까지만 잃습니다. 즉, min⁡(Lj,b)만큼의 점수를 잃습니다. 만약 현재 점수가 a×K라면, 보호 없이 Lj만큼의 점수를 잃습니다.

목표는 승리와 패배의 순서를 최적으로 배치하여 N+M번의 게임 후에 최대한 높은 최종 점수를 얻는 것입니다.

푼 방법

이 문제는 동적 계획법(Dynamic Programming, DP)을 사용하여 해결할 수 있습니다. 각 단계에서 승리와 패배를 선택하는 모든 경우를 고려하여 최적의 결과를 찾아냅니다.

정답 코드

n = int(input())
wins = list(map(int, input().split()))
m = int(input())
loses = list(map(int, input().split()))
k = int(input())

dp = [[float('-inf') for _ in range(m+1)] for _ in range(n+1)]

dp[0][0] = 0
for i in range(1,n+1):
    dp[i][0] = dp[i-1][0] + wins[i-1]
for j in range(1, m+1):
    b = dp[0][j-1] % k
    if b == 0:
        dp[0][j] = dp[0][j-1] - loses[j-1]
    else:
        dp[0][j] = dp[0][j-1] - min(b, loses[j-1])

for i in range(1, n+1):
    for j in range(1, m+1):
        tmp1 = dp[i-1][j] + wins[i-1]
        b = dp[i][j-1] % k
        if b == 0:
            tmp2 = dp[i][j-1] - loses[j-1]
        else:
            tmp2 = dp[i][j-1] - min(b, loses[j-1])
        dp[i][j] = max(tmp1, tmp2)

# for i in range(n+1):
#     print(dp[i])

print(dp[n][m])