[백준] 10835번 카드게임

문제

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

문제요약

1. 두 개의 카드뭉치가 존재한다.

2. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있으며, 이 경우에 오른쪽 카드에 적힌 수만큼 점수를 획득한다.

3. 언제든지 왼쪽만 버리던가 둘 다 버릴 수도 있다.

4. 입력은 첫째줄에 한 더미의 카드의 개수를 나타내는 N, 둘째줄에는 왼쪽 더미의 카드에 적힌 정수, 셋째줄에는 오른쪽 더미의 카드에 적힌 수가 입력된다.

5. 출력은 얻을 수 있는 최종 점수의 최대값을 출력한다.

풀이과정

DP 문제라는 것은 알았지만 DP문제를 많이 풀어보지 않아서 결국 풀이를 보고 해결했다.

1. DP(i,j) = 왼쪽 카드가 i장 남고 오른쪽 카드가 j장 남았을 때 얻을 수 있는 최고 점수

2. DP[x][y]= max(DP[x+1][y],DP[x+1][y+1])

   if(A[x]>B[y]) DP[x][y]=max(DP[x][y],DP[x][y+1]+b[y])

   --> 식을 이용해 해결한다.

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
// N : 한 더미의 카드의 개수
// A : 왼쪽 카드 더미
// B : 오른쪽 카드 더미
// DP[i][j] : 왼쪽 카드뭉치의 카드가 i개 남고 오른쪽 카드가 j장 남았을 때 얻을 수 있는 최고점수
int N, A[2001], B[2001], DP[2001][2001];
int solution(int left, int right)
{
	// 카드 더미가 남아있지 않으면
	if (left == N || right == N) return 0;
	int &val = DP[left][right];
	if (val != 0) return val;
	// 왼쪽 카드의 숫자가 오른쪽 카드의 숫자보다 클 경우면 오른쪽 카드를 버릴 경우와 비교
	// 오른쪽 카드의 숫자가 크면 왼쪽 카드만 버릴 경우와 둘다 버릴 경우를 비교
	val = A[left] > B[right] ? max(val, solution(left, right + 1) + B[right])  : max(solution(left + 1, right), solution(left + 1, right + 1));
	return val;
}
int main()
{
	
	cin >> N;
	//입력
	for (int i = 0; i < N; i++) cin >> A[i];
	for (int i = 0; i < N; i++) cin >> B[i];
	cout << solution(0, 0);
	return 0;
}