【伯俊】10835/カードゲーム
# Appreciation /*
* Problem :: 10835 / 카드게임
*
* Kind :: Dynamic Programming
*
* Insight
* - 이 문제를 Greedy 한 방법으로 풀 수 있을까?
* 도저히 그렇게 풀 수는 없을 것 같다
* + dp[i][j] = 왼쪽 카드를 i개 버리고 오른쪽 카드를 j개 버렸을 때,
* 남은 카드들로 얻을 수 있는 점수의 최댓값
* 이라고 하면, dp[i][j] = max(dp[i+1][j], dp[i+1][j+1])
* 만약, 왼쪽 카드뭉치를 L[N], 오른쪽 카드뭉치를 R[N] 이라고 하면
* if (L[i] > R[j]) { dp[i][j] = max(dp[i][j], dp[i][j+1]+R[j] }
* # 위처럼 DP 로 풀면 되겠다
* -> 우리가 구하고자 하는 값은 위의 dp 정의에 따라 dp[0][0] 이 된다
*/
# Code //
// BOJ
// ver.C++
//
// Created by GGlifer
//
// Open Source
#include <iostream>
#include <cstring>
using namespace std;
#define endl '\n'
// Set up : Global Variables
int N;
int L[2000], R[2000];
int dp[2000][2000];
// Set up : Functions Declaration
int f(int l, int r);
int main()
{
// Set up : I/O
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Set up : Input
cin >> N;
for (int i=0; i<N; i++)
cin >> L[i];
for (int i=0; i<N; i++)
cin >> R[i];
// Process
/* dp[l][r] = 왼쪽 카드 l개를 버리고 오른쪽 카드를 r개 버렸을 때,
* 남은 카드들로 얻을 수 있는 점수의 최댓값 */
memset(dp, -1, sizeof(dp));
/* 게임을 통해 얻을 수 있는 최종 점수의 최댓값 = dp[0][0] */
int ans = f(0, 0);
// Control : Output
cout << ans << endl;
}
// Helper Functions
int f(int l, int r)
/* 왼쪽 카드 l개를 버리고 오른쪽 카드를 r개 버렸을 때,
* 남은 카드들로 얻을 수 있는 점수의 최댓값을 반환 */
{
/* 왼쪽이나 오른쪽 카드들을 모두 버렸다면 더이상 점수를 얻을 수 없음 */
if (l == N || r == N) return 0;
if (dp[l][r] != -1) return dp[l][r];
/* 왼쪽 카드만 버리기, 왼쪽 카드와 오른쪽 카드 둘다 버리기 */
dp[l][r] = max(f(l+1, r), f(l+1, r+1));
if (L[l] > R[r]) { /* 왼쪽 카드 > 오른쪽 카드 */
dp[l][r] = max(dp[l][r], f(l, r+1)+R[r]); /* 오른쪽 카드만 버리기 */
} return dp[l][r];
}
Reference
この問題について(【伯俊】10835/カードゲーム), 我々は、より多くの情報をここで見つけました
https://velog.io/@gglifer/백준-10835-카드게임
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
/*
* Problem :: 10835 / 카드게임
*
* Kind :: Dynamic Programming
*
* Insight
* - 이 문제를 Greedy 한 방법으로 풀 수 있을까?
* 도저히 그렇게 풀 수는 없을 것 같다
* + dp[i][j] = 왼쪽 카드를 i개 버리고 오른쪽 카드를 j개 버렸을 때,
* 남은 카드들로 얻을 수 있는 점수의 최댓값
* 이라고 하면, dp[i][j] = max(dp[i+1][j], dp[i+1][j+1])
* 만약, 왼쪽 카드뭉치를 L[N], 오른쪽 카드뭉치를 R[N] 이라고 하면
* if (L[i] > R[j]) { dp[i][j] = max(dp[i][j], dp[i][j+1]+R[j] }
* # 위처럼 DP 로 풀면 되겠다
* -> 우리가 구하고자 하는 값은 위의 dp 정의에 따라 dp[0][0] 이 된다
*/
//
// BOJ
// ver.C++
//
// Created by GGlifer
//
// Open Source
#include <iostream>
#include <cstring>
using namespace std;
#define endl '\n'
// Set up : Global Variables
int N;
int L[2000], R[2000];
int dp[2000][2000];
// Set up : Functions Declaration
int f(int l, int r);
int main()
{
// Set up : I/O
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Set up : Input
cin >> N;
for (int i=0; i<N; i++)
cin >> L[i];
for (int i=0; i<N; i++)
cin >> R[i];
// Process
/* dp[l][r] = 왼쪽 카드 l개를 버리고 오른쪽 카드를 r개 버렸을 때,
* 남은 카드들로 얻을 수 있는 점수의 최댓값 */
memset(dp, -1, sizeof(dp));
/* 게임을 통해 얻을 수 있는 최종 점수의 최댓값 = dp[0][0] */
int ans = f(0, 0);
// Control : Output
cout << ans << endl;
}
// Helper Functions
int f(int l, int r)
/* 왼쪽 카드 l개를 버리고 오른쪽 카드를 r개 버렸을 때,
* 남은 카드들로 얻을 수 있는 점수의 최댓값을 반환 */
{
/* 왼쪽이나 오른쪽 카드들을 모두 버렸다면 더이상 점수를 얻을 수 없음 */
if (l == N || r == N) return 0;
if (dp[l][r] != -1) return dp[l][r];
/* 왼쪽 카드만 버리기, 왼쪽 카드와 오른쪽 카드 둘다 버리기 */
dp[l][r] = max(f(l+1, r), f(l+1, r+1));
if (L[l] > R[r]) { /* 왼쪽 카드 > 오른쪽 카드 */
dp[l][r] = max(dp[l][r], f(l, r+1)+R[r]); /* 오른쪽 카드만 버리기 */
} return dp[l][r];
}
Reference
この問題について(【伯俊】10835/カードゲーム), 我々は、より多くの情報をここで見つけました https://velog.io/@gglifer/백준-10835-카드게임テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol