[백준 11062] 카드 게임

https://www.acmicpc.net/problem/11062

11062번: 카드 게임

 

근우부터 시작해서 가장 왼쪽, 가장 오른쪽의 카드중 하나를 가져갑니다. 그 다음 명우도 같은 행동을 합니다.

두 사람 모두 최선의 전략으로 행동합니다. 그리고 카드의 합을 구합니다.

이 때 저희가 필요한건 근우가 가진 카드만의 합입니다.

이를 만약 완전탐색만으로 구현한다면 카드의 갯수는 1000개이므로 시간초과가 발생할 것을 예상할 수 있습니다. 

 

이를 해결하기 위해 카드 게임 문제는 dp로 풀어야 합니다.

 

먼저 dp를 이야기하기 전에 문제해결에 필요한 근우의 입장에서 완전탐색으로 최선의 전략을 구현하는 방법을 얘기하겠습니다.

값을 더할 때 근우의 차례이면 최대의 값이 구성하도록 근우의 합에 더해주면 됩니다. 

근우의 차례가 아닌 명우의 차례일 경우 근우가 최소의 합을 구성하는 것이 명우의 최선의 전략입니다.

그러므로 근우가 최소의 합을 구성하도록 선택하게 합니다. 이 때는 명우가 카드를 가지므로 근우의 합에 더하지 않습니다.

(저의 경우에는 dp를 생각하는 것보단 최선의 전략의 뜻을 이해하는게 더 어려웠습니다.)

 

이를 위해서 재귀를 통해 카드가 없을 때 나올 수 있는 모든 상황까지 간 다음 값을 반환하면서 큰 값을 취하는 완전탐색으로 구현합니다. 하지만 위에서 서술했듯이 이 방식은 시간초과가 발생합니다. 

 

dp를 이용해서 해결 하는 방법은 (왼쪽 위치,오른쪽 위치, 차례)가 같을 때 이미 그 상황을 진행했었다면 저장되어 있는 최선의 전략으로 구해져 있는 값을 이용하는 방식입니다.

 

dp에 이용되는 저장된 값은 근우가 가진 카드만의 합을 가지고 있습니다. 이 저장된 값은 갱신되지 않았음을 표기하기 위해 초기값을 전부 1로 설정합니다. 갱신되었다면 0이상이 됩니다.

 

만약 해당 상황을 진행하지 않았었다면 그 상황에서의 최선의 전략으로 값을 구합니다.

 

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
int T,N,arr[1002],dp[1002][1002][2];
int go(int lft,int rght,int turn)
{
    int flag = turn%2; // 1근우 0명우
    if(dp[lft][rght][flag]!=-1) return dp[lft][rght][flag];
    if(lft>=rght)
    {
        if(flag) return dp[lft][rght][flag]=arr[lft];
        else return dp[lft][rght][flag]=0; 
    }
    if(flag) return dp[lft][rght][flag] = max(go(lft+1,rght,turn+1)+arr[lft],go(lft,rght-1,turn+1)+arr[rght]);
    else return dp[lft][rght][flag]= min(go(lft+1,rght,turn+1),go(lft,rght-1,turn+1));
}
void sol()
{
    cin >> N;
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<N;i++)
    {
        cin >> arr[i];
    }
    cout << go(0,N-1,1) << endl;

}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    cin >> T;
    for(int i=0;i<T;i++) sol();
}

 

코드를 작성하고 다른 분들의 코드를 보니 dp값을 레퍼런스를 통해 심플하게 작성한것을 볼 수 있었습니다.

 

코드를 가독성 좋고 클린하게 작성할 수 있도록 발전하도록 노력해야겠다는 생각이 들었습니다.

 

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
int T,N,arr[1002],dp[1002][1002][2];
int go(int lft,int rght,int turn)
{
    int flag = turn%2; // 1근우 0명우
    int &ret = dp[lft][rght][flag];
    if(ret!=-1) return ret;
    if(lft>=rght)
    {
        if(flag) return ret=arr[lft];
        else return ret=0; 
    }
    if(flag) return ret = max(go(lft+1,rght,turn+1)+arr[lft],go(lft,rght-1,turn+1)+arr[rght]);
    else return ret= min(go(lft+1,rght,turn+1),go(lft,rght-1,turn+1));
}
void sol()
{
    cin >> N;
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<N;i++)
    {
        cin >> arr[i];
    }
    cout << go(0,N-1,1) << endl;

}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    cin >> T;
    for(int i=0;i<T;i++) sol();
}

 

이 문제도 그렇지만 dp는 역시 무척이나 어렵습니다.

dp를 생각해내기 쉽지 않다면 해결하기 위한 답은 그저 많은 문제를 풀면서 많은 코드를 보고 경험을 쌓아서 그 경험을 이용하는 것이 최선이라고 생각합니다.