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

1. 문제 풀이

문제의 유형은 dynamic programming입니다. 문제에서 설명한 카드 게임의 규칙을 활용해 점화식을 세우면 간단하게 풀이가 가능합니다. 처음 문제를 읽고 나선 재귀+메모이제이션으로 구현하는 것이 쉬워 보여서 재귀로 구현했습니다. 

 

d[i][j] = k : 왼쪽 카드의 순서가 i+1, 오른쪽 카드의 순서가 j+1일 때, 얻을 수 있는 점수의 최댓값 k

 

문제에선 1-indexed로 카드의 순서가 설명되어 있고 저는 카드 순서를 0-indexed로 해서 테이블 정의는 위와 같이 적었습니다. 다음은 설명되어 있는 규칙에 맞추어서 재귀호출하여 풀이하였습니다.

 

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';
int n, l[2005], r[2005], d[2005][2005];
int solve(int lidx, int ridx){
  if(lidx == n || ridx == n) return 0;
  if(d[lidx][ridx] != -1) return d[lidx][ridx];
  d[lidx][ridx] = max(solve(lidx+1, ridx), solve(lidx+1, ridx+1));
  if(l[lidx] > r[ridx]) d[lidx][ridx] = max(d[lidx][ridx], solve(lidx, ridx+1) + r[ridx]);
  return d[lidx][ridx];
} 
int main() {
  fastio(nullptr, false);
  cin >> n;
  for(int i = 0; i < n; i++) cin >> l[i];
  for(int i = 0; i < n; i++) cin >> r[i];
  memset(d, -1, sizeof(d));
  cout << solve(0, 0);
}

 

3. 제출 결과