BOJ 10835 카드게임

 

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

10835번: 카드게임

그리디 알고리즘인가?

- 항상 오른쪽 카드만 버릴수 있으면 정답인가? NO

 

플레이 가능한 동작은 3가지이다

(1) 왼쪽 카드만 버리기

(2) 왼쪽 카드와 오른쪽 카드 모두 버리기

(3) 오른쪽 카드만 버리기 (단, 오른쪽 카드의 숫자가 작아야 하고, 이때 득점이 가능하다)

 

만약 카드가 1장씩 남아있다면? 위의 (1) ~ (3) 연산을 if를 통해 점수를 얻을 수 있다.

 

만약 왼쪽에 1장, 오른쪽에 2장이 남아있다면?

(1) 연산을 하면 오른쪽에 2장이 남는다

(2) 연산을 하면 오른쪽에 1장이 남는다

(3) 연산이 가능하다면 위의 카드가 1장씩 남아있는 경우가 된다

 

이런식으로 카드를 쌓아가면 재귀적 구조가 있음을 알 수 있다 -> 다이나믹 프로그래밍

그런데 재귀식을 작성하기 여간 어려운 것이 아니다

bottom-up으로 식을 작성하기 어렵기 때문에 top-down 방식으로 문제를 해결하는 것이 좋아보인다

 

/**
 * a: the index of left cards
 * b: the index of right cards
 * N: the number of cards
 * A: the array of the left cards
 * B: the array of the right cards
 
 * return: the maximum score of the game
 */
int dfs(int a, int b){
    // Out of range -> there is no way to gain score
    if (a >= N || b >= N) return 0;
    
    // already calculated
    if (dp[a][b] != -1) return dp[a][b];

    dp[a][b] = max(dfs(a + 1, b + 1), dfs(a + 1, b));
    if(A[a] > B[b]){
        dp[a][b] = max(dp[a][b], dfs(a, b + 1) + B[b]);
    }
    return dp[a][b];
}

 

전체 코드는 다음과 같다

#include <iostream>
#include <vector>
 
using namespace std;
 
void IOSetup();

int N;
vector<int> A, B;
vector<vector<int>> dp;

int dfs(int a, int b){
    if (a >= N || b >= N) return 0;
    if (dp[a][b] != -1) return dp[a][b];

    dp[a][b] = max(dfs(a + 1, b + 1), dfs(a + 1, b));
    if(A[a] > B[b]){
        dp[a][b] = max(dp[a][b], dfs(a, b + 1) + B[b]);
    }
    return dp[a][b];
}

int main() {
    IOSetup();

    cin >> N;
    A.resize(N);
    B.resize(N);
    dp.resize(N + 1, vector<int>(N + 1, -1));

    for (int i = 0; i < N; i++) { cin >> A[i]; }
    for (int i = 0; i < N; i++) { cin >> B[i]; }

    int ans = dfs(0, 0);
    cout << ans << "\n";

    return 0;
}
 
void IOSetup() {
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}