BOJ 10835 카드게임

문제설명

접근방식 or 주절주절

스터디를 함께 하는 분이 제시해준 문제로 우선은 주제가 DP라서 DP풀이로 접근할 수 있었다.
여름방학 때는 왜 DP인지도 모르고 헷갈려만 하다가 2학기 알고리즘 강의를 수강하면서 나름 개념이 잡혔다고 자부하던 터라 DP 점화식을 세운 뒤로는 매우 당당하게 코드를 써내려갔다.


그런데 "틀렸습니다"가 뜨고 약 한 시간 정도 지난한 부분수정만 하다보니 완전히 잘못된 접근법이라는 것을 깨달았다. 다행히도 DP에 대한 나의 이해도 자체가 틀린 것은 아니지만 처음 DP를 헷갈리게 했던 부분을 다시 마주하게 됐다는 것을 알게 되었다. 현재 내가 익숙해하는 DP 풀이방식은 Bottom-Up 방식으로 개인적으로 느끼기에는 DP 배열을 할당해서 부분합들을 합쳐나가는 개념에 이상적으로 적합한 방식이라고 생각한다. 부분문제의 최적해가 전체문제의 최적해라는 개념과 중복되는 부분문제의 조합으로 전체문제를 풀이해가는 것이 반복문의 낮은 인덱스부터 초기값을 설정하고 쌓아올라가는 것이라고 생각했다.


하지만 이 문제에서 요구하는 방식은 그리고 웃기게도 바로 이전 포스팅에 올린 BOJ1937 욕심쟁이판다 문제에서 너무 당연하게 활용했던 재귀적 호출을 이용한 Top-Down DP 방식이다. 재귀적인 함수 호출을 통해 부분문제를 해결해간다는 점이 분할정복 기법과 유사하다고 생각해서 그동안은 DP라고 믿고 싶지 않았던 풀이였는데... 이제는 마주할 수 밖에 없다는 생각에 그렇다면 어떻게 Bottom-Up과 Top-Down 방식 중 무엇이 더 적합한지를 판별할 기준을 생각해보았다.


핵심은 예외처리라고 이번 문제에서는 느꼈다. 다른 스터디원분이 Bottom-Up 방식으로 문제를 풀이하신 것을 봤지만 그 예외처리 방식이 직관적으로 떠오를 수 있는 방식은 아니라고 생각했다.이번 문제에서는 오른쪽 카드가 왼쪽 카드보다 작은 경우에만 오른쪽 카드를 빼면서 점수를 추가할 수 있는 조건이 붙어있는데 Bottom-Up 방식의 배열 전체를 처리하는 풀이를 하다보면 사실상 불가능한 경우의 수 값도 처리하는 것이 문제였던 것이다. 반면에 Top-Down 방식으로 풀이하게 되면 직관적으로 실제 플레이하는 듯한 직관을 받으면서 풀이할 수 있었다.


아예 새로운 문제를 마주해서 이것이 DP임을 결정하고 그 안에서 또 BU와 TD를 결정하는 것은 더 많은 문제 예시를 통해서 경험해봐야겠지만 이번 문제를 통해서 그 구분점에 대한 인식을 명확하게 체감하게 된 것 같아서 긍정적이다.

DP 정확히 이해하기

핵심 아이디어

DP[i][j] : 왼쪽 덱의 i번째 카드, 오른쪽 덱의 j번째 카드가 각각 맨 위에 있을 때 얻을 수 있는 최대 값
1번, 2번 기준은 항상 기본으로 탐색 가능하므로 기본적으로 두 값 중 큰 값을 기본값으로 설정하고

dp[i][j] = max(DFS(i+1, j+!1), DFS(i+1, j)

실제 덱에서의 카드 크기 비교를 통해서 3번 기준이 가능하면 추가로 더 확인해준다.

if(A[i] > B[j])
	dp[i][j] = max(dp[i][j], DFS(i, j+1)+B[j]    

C++ 코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair <ll, ll>;

vector<vector<int>> dp;
vector<int> A;
vector<int> B;
int N;

int DFS(int l, int r){
  if(l >= N+1 || r >= N+1)
    return 0;

  if(dp[l][r] == -1){
    int score = max(DFS(l+1, r+1), DFS(l+1, r));
    if(A[l] > B[r])
      score = max(score, DFS(l, r+1) + B[r]);
    dp[l][r] = score;
  }

  return dp[l][r];
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  //freopen("inp.txt", "r", stdin);
  
  // input 
  cin >> N;
  A.resize(N+1);
  B.resize(N+1);
  dp.resize(N+1, vector<int>(N+1, -1));
  for(int i=1; i<=N; i++)
    cin >> A[i];
  for(int i=1; i<=N; i++)
    cin >> B[i];

  cout << DFS(1, 1);
}