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

문제링크 : https://www.acmicpc.net/problem/10835

10835번: 카드게임

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N;
int a[2001], b[2001];
int dp[2001][2001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;

    for(int i=N; i>0; i--)	cin >> a[i]; //마지막 카드부터
	for(int i=N; i>0; i--)	cin >> b[i];


    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=N; j++)
        {
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]); //모두 버리거나, 왼쪽만 버림
            if(a[i]>b[j]) dp[i][j] = max(dp[i][j], dp[i][j-1]+b[j]); //현재값과 오른쪽 하나버리고 더한 값 비교
        }
    }

    cout <<dp[N][N];

    return 0;
}

 

점화식 자체는 문제의 주어진 조건에 따라 그대로 작성해주면 된다.

처음에 모두 버리거나, 왼쪽만 버리므로 한쪽은 [i-1][j-1]을, 나머지 한쪽은 왼쪽만 버리므로 [i-1][j]이 된다.

 

본격적으로 값을 갱신하는 부분은 왼쪽 값이 오른쪽 값보다 클 떄이다.

오른쪽 값을 하나 버리고 현재 오른 값을 현재 dp에 더해준다.

왼쪽을 버릴떄 [i-1][j]이었으므로 오른쪽은 [i][j-1]이다. 여기에 현재 오른쪽 값 b[j]을 더해준다.

 

해당 문제에서 주의할 점은 입력 순서를 거꾸로 받은 것이다.

2중 반복문에서 값을 갱신해줄 때 직전값을 검토하여 갱신해주기 때문에 저장되는 값은 역순이다.