[AtCoder] Flipping and Bonus(DP)

https://atcoder.jp/contests/abc261/tasks/abc261_d

D - Flipping and Bonus

DFS로 문제를 풀었는데, 시간이 초과되어서 결국 컨테스트 시간 내에 해결하지 못한 문제이다.

 

[문제 해석]

1부터 $i$번째 코인부터 던져서 만약 head가 나오면 카운터를 1 증가하고, $X_i$ 엔을 받는다.

만약 tail이 나오면, counter를 0으로 리셋하고 돈을 받을 수 없다.

 

추가적으로 M개의 스트라이크 보너스가 있다. $i$번째 스트레이크 보너스는 카운터가 $C_i$에 도달할 때마다 $Y_i$ 엔을 제공한다.

 

이를 통해 Takahashi가 최종적으로 받을 수 있는 최대 금액을 도출해야 한다.

 

 

처음에 DFS로 풀 때는 동전마다 순회하면서 해당 동전이 head인 경우, tail인 경우를 모두 try 해서 maximum amount of money를 갱신하려고 했다.

그런데 이보다 더 효율적인 방법이 있다니?!

결국 공식 Editorial을 펼쳐보고 말았다.

역시나 2순위로 예상했던 DP로 해당 문제를 더 효율적으로 풀 수 있었다.

아무래도 각각의 동전의 뒤집기 여부가 독립적이기 때문에 가능한 것 같다.

 

[해설 번역]

가장 중요한 사실은 $0 <= i <= N - 1$에서 만약 우리가 $i$번째 토스가 끝났을 때의 카운터 $C$의 값을 안다면 $(i + 1)$ 번째에서 우리가 벌 수 있는 돈의 최대값은 1번부터 i번까지의 동전 토스의 결과에 독립적이다.

따라서 "after the first i tosses", "the value of the counter becomes j"의 조건을 통해 충분히 점진적으로 1번부터 i번까지의 토스를 통해 얻은 돈의 최대값을 업데이트할 수 있다. 이러한 최대값을 $dp[i][j]$라 하자. 만약 $i < j$에서 특정 상황이 불가능하다면, dp[i][j] = $-\infty$이다.

첫 번째로 우리는 초기값으로 $dp[0][j]$을 고려한다. 초기 카운터는 0이기 때문에 $dp[0][0] = 0, dp[0][j] = - \infty (j > 0)$.

두 번째로 우리는 DP 배열을 업데이트할지를 고민해야 한다. 우리가 $dp[i][j](0 <= i <= i_0)$의 값을 얻었을 때 $dp[i_0 + 1][j]$를 어떻게 연산할지를 고려해야 한다.

 

1) $j_0 > 0$을 고려해보자. 이러한 경우는 $i_0$번째 토스 이후 카운터가 $i_0 - 1$ 되어야 하고 코인은 $i_0 + 1$번째 토스에서 head가 나와야 한다. 조금 더 쉽게 말하자면 점화식의 기준을 카운터가 1 증가하는 것으로 삼는다.

카운터가 a로 증가하려면 head가 나와야 하고, 이전 카운터가 a - 1이어야 한다.

 

$dp[i_0 + 1][j_0] = dp[i_0][j_0 - 1] + X_{i_0 + 1} + B_{j_0}$

$B_{j_0}$는 스트레이크 보너스

 

$j_0 = 0$은 오직 코인이 $i_0 + 1$번째 토스에서 tail이 나올 때만 가능하다. 따라서 아래와 같은 점화식이 가능하다.

 

$dp[i_0 + 1][0] = max_j(dp[i_0][j])$

참고로 $dp[i_0][j] = -\infty$이므로 만약 $i_0 < j$라면 $dp[i_0 + 1][0] = max_{0 <= j <=i_0}(dp[i_0][j])$이다.

 

결국 최종적인 점화식은 $max_{0 <= j <=i_0}(dp[N][j])$이다.

 

전체적인 복잡도는 $O(N^2)$이다.

 

아무래도 점화식이 head, tail로 나뉘어 복잡하다보니 한국어로 충분히 설명히 되지 않았어서 주석을 달면서 다시 한 번 정리해보았다.

 

#include <iostream>
#include <algorithm>

using namespace std;
int main(void) {
    int n, m;
    long long x[5001];
    long long c, y;
    long long b[5001];
    long long dp[5001][5001];
    long long ans;
    
    cin >> n >> m;
    for(int i = 0;i <= n;i++) b[i] = 0;
    
    // 코인 1번부터 보상
    for(int i = 0;i < n;i++) cin >> x[i + 1];
    // 카운터별 보상
    for(int i = 0;i < m;i++) {
        cin >> c >> y;
        b[c] = y;
    }
    // i번째 코인까지 고려, j번째 카운터
    dp[0][0] = 0;
    for(int i = 1;i <= n;i++) {
        // head인 경우
        for(int j = 1;j <= i;j++) {
            dp[i][j] = dp[i - 1][j - 1] + x[i] + b[j];
        }
        // 초기화
        dp[i][0] = 0;
        // tail인 경우도 고려
        // 어떤 코인에서 꼬리가 나오든 카운터는 0이 되므로 코인별로 순회하면서 최댓값으로 갱신
        for(int j = 0;j < i;j++){
            dp[i][0] = max(dp[i][0], dp[i - 1][j]);
        }
    }
    ans = 0;
    for(int i = 0;i <= n;i++) {
        ans = max(ans, dp[n][i]);
    }
    cout << ans << '\n';
}