[ 프로그래머스 카드 게임 (Lv4) ] (C++)

프로그래머스의 카드게임(Lv4) 문제이다.

[ 문제풀이 ]

먼저, 카드게임의 규칙에 대해서부터 다시한번 정리를 해보고 문제풀이에 들어가보자.

규칙1. 언제든지 왼쪽 카드와 오른쪽 카드를 둘 다 버릴 수 있다. 이 때 얻는 점수는 없다.

규칙2. 언제든지 왼쪽 카드만 버릴 수 있다. 이 때 얻는 점수는 없다.

규칙3. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작다면, 오른쪽 카드만 버릴 수 있다. 이 때 오른쪽 카드에 적힌 수만큼

           점수를 얻게 된다.

규칙4. 왼쪽이든 오른쪽이든 어느 한 쪽에 남은 카드가 없다면 게임이 종료된다.

이렇게 총 4가지의 규칙이 있는데, 규칙4는 게임이 종료되는 조건이기 때문에 점수를 얻는 것과는 크게 상관이 없다.

즉, 점수를 얻거나, 얻기 위한 과정으로 규칙 1, 2, 3 을 잘 조합해야 한다는 것을 의미한다.

본인은 이 문제를 깊이우선탐색(DFS)와 메모이제이션을 이용해서 접근하였다.

먼저, 사용한 핵심 변수로는 DP[][] 라는 int형 2차원 배열이 있는데, 이 배열의 값이 의미하는 것은 다음과 같다.

DP[a][b] = c 의 의미는 "왼쪽 카드 더미에 a번째 카드가 가장 위에 있고, 오른쪽 카드 더미에 b번째 카드가 가장 위에 있을 때, 얻을 수 있는 최대점수는 c점입니다." 이다.

탐색을 위한 함수인 DFS함수에서는 2개의 매개변수를 사용해 주었다. 현재 왼쪽 카드더미에서 몇 번째 카드가 왼쪽 카드더미의 가장 위에 있는지와 오른쪽 카드 더미에서 몇 번째 카드가 오른쪽 카드 더미의 가장 위에 있는지를 나타내는 2개의 변수이다.

쉽게 생각해서, 왼쪽 카드 더미의 현재 Index번호와, 오른쪽 카드 더미의 현재 Index번호 2개를 매개변수로 사용한 것이다.

실질적인 구현 내용은 "현재 상태에서, 위에서 말한 3개의 규칙으로 실행했을 때의 최댓값을 저장" 하는 방식으로 구현하였다.

int DFS(int L_Idx, int R_Idx)
{
    if (L_Idx == Left.size() || R_Idx == Right.size()) return 0;
    if (DP[L_Idx][R_Idx] != 0) return DP[L_Idx][R_Idx];
    
    int Case1 = DFS(L_Idx + 1, R_Idx + 1);
    int Case2 = DFS(L_Idx + 1, R_Idx);
    int Case3 = -1;
    if (Right[R_Idx] < Left[L_Idx]) Case3 = DFS(L_Idx, R_Idx + 1) + Right[R_Idx];
 
    DP[L_Idx][R_Idx] = Bigger(Bigger(Case1, Case2), Case3);
    return DP[L_Idx][R_Idx];
}

위의 코드는 본인이 직접 구현한 실제 DFS의 코드이다.

line3) 의 조건문은 '규칙4'를 의미한다. 어느 쪽 카드 더미이든, 더 이상 카드가 존재하지 않으면 그대로 게임을 종료시켜야 한다.

이 때, 게임을 종료시킴으로써 얻는 점수는 없으므로 0을 return 시켜주는 것이다.

line4) 는 '메모이제이션'을 적용시켜준 것이다. "기존에 한번이라도, 현재 상태를 계산해본 적이 있다면, 더 이상의 탐색을 하지 않고 기존에 계산했었던 값을 그대로 가져오는 것" 을 구현한 것이다.

line6, 7, 8)은 규칙 1, 2, 3을 순차적으로 구현한 것이다. 물론 규칙3에는 조건이 하나 필요하기 때문에, line9)와 같은 조건을 걸어준 것이다.

line11)에서는 "현재 상태에서 가질 수 있는 최댓값"을 저장하는 과정이다.

[ 소스코드 ]

#include <string>
#include <vector>
 
#define MAX 2010
using namespace std;
 
int DP[MAX][MAX];
vector<int> Left;
vector<int> Right;
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
int DFS(int L_Idx, int R_Idx)
{
    if (L_Idx == Left.size() || R_Idx == Right.size()) return 0;
    if (DP[L_Idx][R_Idx] != 0) return DP[L_Idx][R_Idx];
    
    int Case1 = DFS(L_Idx + 1, R_Idx + 1);
    int Case2 = DFS(L_Idx + 1, R_Idx);
    int Case3 = -1;
    if (Right[R_Idx] < Left[L_Idx]) Case3 = DFS(L_Idx, R_Idx + 1) + Right[R_Idx];
 
    DP[L_Idx][R_Idx] = Bigger(Bigger(Case1, Case2), Case3);
    return DP[L_Idx][R_Idx];
}
 
int solution(vector<int> left, vector<int> right) 
{    
    Left = left;
    Right = right;
    int answer = DFS(0, 0);
    return answer;
}