[ 백준 10835 ] 카드게임 (C++)

백준의 카드게임(10835) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

주어진 규칙에 맞게 카드게임을 진행했을 때, 얻을 수 있는 최댓값을 구해야 하는 문제이다.

본인은 이 문제를 완전탐색, 그 중에서도 DFS(깊이 우선 탐색)을 이용해서 접근하였다.

탐색을 진행하는 중에 있어서도, 중복된 계산을 최소화 시켜주기 위해서 메모이제이션을 이용해서 구현하였다.

이 과정에서 대해서 지금부터 구체적으로 알아보도록 하자.

먼저, 수식을 하나 정해놓고 시작해보자.

F[A][B] = C 라는 수식을 사용할 것인데, 이 수식의 의미는 "왼쪽더미에 A번 카드가 가장 위에 있고, 오른쪽 더미에 B번 카드가 가장 위에 있을 때, 얻을 수 있는 최대점수는 C점입니다." 를 의미한다.

그럼 지금부터 이를 바탕으로 DFS함수에 대해서 구체적으로 알아보자.

#1. 탐색 함수의 인자

재귀를 이용한 완전탐색을 진행하기 위해서 재귀로 사용될 함수의 인자부터 알아보자.

본인은 2개의 변수를 인자로 사용해 주었다. 바로, "왼쪽더미의 가장 위에 있는 카드 번호" 와 "오른쪽 더미의 가장 위에 있는 카드 번호" 를 인자로 사용해 주었다.

가장 초기에는 왼쪽 더미와 오른쪽 더미 모두 1번 카드가 가장 위에 있을 것이다. 따라서 호출은 (1 , 1)로 호출이 될 것이다.

그리고 이 호출을 시작으로 탐색을 진행하게 될 것이다.

#2. 탐색 부분

게임을 진행할 때에는 3가지 규칙이 있다.

1. 왼쪽 카드만 한 장 버릴 수 있다.

2. 왼쪽 카드와 오른쪽 카드를 동시에 한 장씩 버릴 수 있다.

3. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에 오른쪽 카드만 한 장 버릴 수 있다.

이렇게 3가지 규칙이 있다. 탐색을 하는 부분에서는 위의 3가지 과정을 모두 탐색을 해 주었다. 동시에 얻을 수 있는 점수 또한 우리가 위에 선언해 놓은 수식에 저장해 주었다.

함수의 이름을 DFS(Left_Idx, Right_Idx) 라고 가정했을 때, 위의 규칙들은 다음과 같이 계산이 되어진다.

1. 왼쪽 카드만 한 장 버릴 수 있다 : DFS(Left_Idx + 1 , Right_Idx)

- DFS함수의 인자로는 왼쪽더미의 가장 위에 있는 카드의 번호와 오른쪽 더미의 가장 위에 있는 카드 번호이기 때문에,

  이 상태에서 왼쪽 카드만 한 장 버린다는 것은, 왼쪽 더미의 가장 위에 있는 카드의 번호가 1만큼 증가한다는 것을 의미한다.

  따라서 위와 같이 계산을 할 수 있다.

  이 때 얻을 수 있는 점수는 없기 때문에 별도로 점수를 더해주는 과정은 필요 없다.

2. 왼쪽 카드와 오른쪽 카드를 동시에 한 장씩 버릴 수 있다 : DFS(Left_Idx + 1 , Right_Idx + 1)

- 위의 함수는 양쪽의 카드를 동시에 한 장씩 버리는 경우이다. 규칙1에서의 설명과 같은 원리로, 가장 위에 있는 카드를 한 장

  씩 버리게 되면, 가장 위에 있는 카드의 번호가 1만큼 증가함을 의미한다.

3. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에 오른쪽 카드만 한 장 버릴 수 있다.

- 이 경우에는 조건부로 탐색을 진행할 수 있다.

  먼저 그 조건은 왼쪽 카드에 적힌 수가 오른쪽 카드에 적힌 수보다 더 커야 한다는 것이다.

  즉, 왼쪽카드[Left_Idx] > 오른쪽카드[Right_Idx] 라는 조건이 성립해야 한다.

  이 조건을 만족한다면, 다음과 같이 함수를 호출할 수 있다.

  DFS(Left_Idx, Right_Idx + 1) + 오른쪽카드[Right_Idx]

  이 경우에는 점수를 얻을 수 있기 때문에 위의 수식과 같이 + 적으로 점수를 얻을 수 있는 식이 추가되어진다.

이 3가지 경우를 모두 탐색하면서 이 때의 최댓값을 우리가 위에서 선언해 놓은 수식에 저장해 주면 된다.

#3. 탐색 종료 설정

더 이상 게임을 진행할 수 없는 타이밍이 더 이상 탐색을 할 수 없는 타이밍과 동일하다.

즉, DFS함수의 매개변수로 주어지는 Left_Idx와 Right_Idx 중 어느 하나라도 N 장을 넘어선다면, 더 이상 게임을 진행할 수 없음을 의미하므로, 이를 탐색 종료부분으로 설정해 줄 수 있다.

[ 소스코드 ]

#include <iostream>
#include <cstring>
 
#define endl "\n"
#define MAX 2010
using namespace std;
 
int N;
int Card_A[MAX];
int Card_B[MAX];
int DP[MAX][MAX];
 
int Max(int A, int B) { return A > B ? A : B; }
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> Card_A[i];
    for (int i = 1; i <= N; i++) cin >> Card_B[i];
}
 
int DFS(int L_Idx, int R_Idx)
{
    if (L_Idx > N || R_Idx > N) return 0;
    if (DP[L_Idx][R_Idx] != -1) return DP[L_Idx][R_Idx];
    
 
    DP[L_Idx][R_Idx] = 0;
    DP[L_Idx][R_Idx] = Max(DFS(L_Idx + 1, R_Idx + 1), DFS(L_Idx + 1, R_Idx));
    if (Card_A[L_Idx] > Card_B[R_Idx]) DP[L_Idx][R_Idx] = Max(DP[L_Idx][R_Idx], DFS(L_Idx, R_Idx + 1) + Card_B[R_Idx]);
    
    return DP[L_Idx][R_Idx];
}
 
void Solution()
{
    memset(DP, -1, sizeof(DP));
    int Answer = DFS(1, 1);
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}