[백준 10835번] 카드게임 (C++)

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

10835번: 카드게임

 

1. 왼쪽 카드만 버리는 경우

2. 왼쪽 카드와 오른쪽 카드를 버리는 경우

3. "왼쪽 카드 < 오른쪽 카드" 를 만족하여 오른쪽 카드만 버리는 경우

이 세가지 경우를 모두 고려해주어야 한다.

dp[left][right] 는 왼쪽 카드와 오른쪽 카드를 left장, right장 버렸을 때 점수의 최댓값이다.

 

코드는 다음과 같다.

#include <iostream>
#include <algorithm>
using namespace std;
int n;
int dp[2001][2001];
int leftCard[2001];
int rightCard[2001];
int solve(int left, int right){
    if(left >= n || right >= n) return 0;
    if(dp[left][right] != -1) return dp[left][right];
    dp[left][right] = max(solve(left+1,right+1), solve(left+1,right));
    if(leftCard[left] > rightCard[right]){
        dp[left][right] = max(dp[left][right], solve(left,right+1)+rightCard[right]);
    }

    return dp[left][right];
}


int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    fill(&dp[0][0],&dp[2000][2001],-1);
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> leftCard[i];
    }
    for(int i = 0; i < n; i++){
        cin >> rightCard[i];
    }
    cout << solve(0,0);
}

 

 

 

2차원 배열을 (0,0)부터 (n,n)까지 초기화 할때 fill(&arr[0][0],&arr[n-1][n], value)의 형식으로 써주면 value 값으로 초기화 할 수 있다.

아직 dp를 보면 피보나치 수열만 생각나고 dp의 개념이 잡히지 않았다면, 재귀로 dp문제를 푸는 것을 추천한다. 재귀 함수 부분을 통해 규칙을 그대로 써 나가면 된다. 처음에 dp문제를 접하면 어떻게 접근해야할지가 고민인 경우가 많은데 위와 같이 짜니 코드를 이해하기 쉽고 접근도 감이 잡힐 거 같다.(물론 나도 아직 Dp가 뭔지 잘 모르겠다..)