[프로그래머스] 카드 게임

문제  : Level4  카드 게임

[ 문제출처 ]   https://programmers.co.kr/learn/courses/30/lessons/42896

 

[ 문제풀이 ]  

 

처음에 문제를 이해 하기를 문제에서 제시된 조건 1 부분에서

1. 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다.  이때 얻는 점수는 없다

이 부분에서 이해가 가질 않았다 역시 국어를 못하니 문제를 빠르게 파악하지를 못하는 것 같다 ㅠㅠ

제시된 조건도 1과 2로 나누어 주었으면 좋지 않았나 싶기도 하다 얻는 점수가 없는 경우를 묶어서 조건으로 내민 것 같다

 

게임에서 가능한 경우를 보자

 

조건 : 어느쪽 더미든 카드가 없어질 때까지

1. 왼쪽 카드를 버리자

2. 왼쪽과 오른쪽 카드를 동시에 버리자

3. 왼쪽 카드 숫자가 오른쪽 카드 숫자보다 크다면 오른쪽 카드를 버린다 (이 때는 오른쪽 카드 숫자만큼 점수를 얻음)

 

처음에 문제를 풀 때 dp 문제인 것을 알고 dp 문제가 그러하듯 정형화된 방식으로 접근을 해보았다.

 

1. 상향식 다이나믹 프로그래밍

2. 재귀 + 메모제이션 

 

1. 상향식 다이나믹 프로그래밍 방법을 이용해서 풀어 보려고 했지만 풀이를 찾지 못했다.. 하지만 2번을 사용하면 주어진

게임 규칙을 간단하게 코드에 적용할 수 있다 여기서 메모이제이션을 사용하는 이유는 말 그대로 메모(기록)를 함으로써

반복되는 계산을 줄이기 위해서다 

 

 

밑에 그림과 같이

모두 5개의 카드 2개의 더미로 게임을 시작한다고 가정을 해보자 

그림과 같이 주어진 게임 규칙 1, 2, 3을 적용시키면 3가지의 부분 문제로 나뉘게 된다.

물론 3번을 적용시키기 위해서는 조건(오른쪽 숫자가 작아야 적용 가능)이 존재하지만 편의상 강제적으로 넣어 보았다.

 

 

위에 그림과 같이 반복되는 부분 문제의 계산을 줄이기 위해서 메모 방식을 사용한다. 

딱 그림에서도 보이듯이 문제를 해결 하기 위해서 메모 방식을 2차원 배열 방식으로 하면 좋을 것 같다. 

왼쪽 카드 개수와 오른쪽 카드 개수로 말이다! 

 

밑에 소스 코드를 보면 간단하게 문제에 주어진 규칙을 적용시킨 것을 볼 수 있다

 

[ 소스 코드 ]  

#include <string>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int MAX = 2000;
int dp[MAX][MAX];
int dfs(const vector<int>& left, const vector<int>& right, int l, int r) {
    if (l == left.size() || r == right.size()) return 0;
    int& ret = dp[l][r];
    if (ret != -1) return ret;
    ret = max(ret, dfs(left, right, l + 1, r));
    ret = max(ret, dfs(left, right, l + 1, r + 1));
    if (left[l] > right[r]) ret = max(ret, dfs(left, right, l, r + 1) + right[r]);
    return ret;
}
int solution(vector<int> left, vector<int> right) {
    memset(dp, -1, sizeof(dp));
    int answer = dfs(left, right, 0, 0);
    return answer;
}