[Algorithm]Baekjoon 10835번 : 카드게임

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

10835번: 카드게임

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
int n;
int leftCards[2005] = { 0 };
int rightCards[2005] = { 0 };
int dp[2005][2005] = { 0 };
 
int DFS(int leftCardIndex, int rightCardIndex)
{
    if (leftCardIndex == n + 1 || rightCardIndex == n + 1) return 0;
    if (dp[leftCardIndex][rightCardIndex] != -1) return dp[leftCardIndex][rightCardIndex];
    
    int result = 0;
 
    if (rightCards[rightCardIndex] < leftCards[leftCardIndex])
    {
        result = DFS(leftCardIndex, rightCardIndex + 1) + rightCards[rightCardIndex];
    }
    else
    {
        result = max(result, DFS(leftCardIndex + 1, rightCardIndex));
        result = max(result, DFS(leftCardIndex + 1, rightCardIndex + 1));
    }
 
    return dp[leftCardIndex][rightCardIndex] = result;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> leftCards[i];
    }
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> rightCards[i];
    }
 
    memset(dp, -1, sizeof(dp));
 
    cout << DFS(1, 1);
}

 

 

좌,우측 카드의 남은개수를 dp테이블로잡고 업데이트해나가면 된다.

 

항시 선택가능한 분기점으로는 좌측카드만 선택, 좌,우측 둘 다 선택이 있다.

대신 점수는 누적안된다.

 

조건부로 선택가능한 분기점으로는 우측카드가 좌측카드보다 값이 작을경우, 우측카드를 선택할 수 있고 값을 누적시킨다.

 

이런 문제에서 제일 주의할 점은, dp값이 '0'이 나올 수 있다는 것. 그러니 초기 dp값은 0으로 초기화되어있으면 안되고 더 낮은값으로 초기화되있어야 한다.