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

문제 설명

카드게임이 있다. 게임에 사용하는 각 카드에는 양의 정수 하나가 적혀있고 같은 숫자가 적힌 카드는 여러 장 있을 수 있다. 게임방법은 우선 짝수개의 카드를 무작위로 섞은 뒤 같은 개수의 두 더미로 나누어 하나는 왼쪽에 다른 하나는 오른쪽에 둔다.

각 더미의 제일 위에 있는 카드끼리 서로 비교하며 게임을 한다. 게임 규칙은 다음과 같다. 지금부터 왼쪽 더미의 제일 위 카드를 왼쪽 카드로, 오른쪽 더미의 제일 위 카드를 오른쪽 카드로 부르겠다.

1. 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다.
2. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.
3. (1)과 (2)의 규칙에 따라 게임을 진행하다가 어느 쪽 더미든 남은 카드가 없다면 게임이 끝나며 그때까지 얻은 점수의 합이 최종 점수가 된다.

왼쪽 더미의 카드에 적힌 정수가 담긴 배열 left와 오른쪽 더미의 카드에 적힌 정수가 담긴 배열 right가 매개변수로 주어질 때, 얻을 수 있는 최종 점수의 최대값을 return 하도록 solution 함수를 작성하시오.

제한 사항

• 한 더미에는 1장 이상 2,000장 이하의 카드가 있다.
• 각 카드에 적힌 정수는 1 이상 2,000 이하이다.

입출력 예

left	right	return
[3, 2, 5]	[2, 4, 1]	7

먼저 오른쪽 카드를 버려서 2점을 획득한다.
그 뒤 왼쪽 카드를 두 장 버리고 오른쪽 카드를 버려서 4점을 획득한다.
마지막으로 오른쪽 카드를 버려서 1점을 획득한다.
총 얻을 수 있는 점수는 7점이다.

풀이)

왼쪽, 오른쪽 카드 더미 각자 최대 2000장까지 있을 수 있으므로, 완전 탐색시 효율성 면에서 시간초과가 난다.

dp를 이용해서 풀어야 하는 문제이다.

배열 dp를 선언해서 풀어줬다.

int dp[2000][2000];// dp[i][j] = 왼쪽 카드 인덱스가 i, 오른쪽 카드 인덱스가 j일 때 나올 수 있는 최대 점수

풀이과정

1. 초기 dp배열을 모두 -1로 초기화한다. dp[0][0] = 0;으로 초기화

2. 이중 포문을 통해, 카드가 나올 수 있는 경우 배열 값을 바꿔준다.

  2.1 왼쪽 카드값이 오른쪽 카드값보다 클때 

       -> 현재 카드가 i, j 인덱스일때  

dp[i][j] += right[j]; //오른쪽 카드 값 더해줌

      dp[i][j+1] = max(dp[i][j+1], dp[i][j]);// 오른쪽 카드 버린 경우 값이 현재 점수 값보다 작으면 바꿔줌

  2.2 왼쪽 카드값이 오른쪽 카드값보다 작을때

      -> 현재 카드가 i, j 인덱스일때

dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]); // 왼쪽, 오른쪽 카드 버린 경우 값이 현재 점수 값보다 작으면 바꿔줌

dp[i+1][j] = max(dp[i+1][j], dp[i][j]);// 왼쪽 카드 버린 경우 값이 현재 점수 값보다 작으면 바꿔줌

3. 왼쪽카드가 모두 없어졌을때, 오른쪽 카드가 모두 없어졌을 때를 다 살펴서 최고 점수 값을 구함

코드)

#include <string>
#include <vector>
#include<algorithm>
using namespace std;

int dp[2000][2000];
int solution(vector<int> left, vector<int> right) {
    int answer = 0;
    for(int i=0;i<left.size();i++){
        fill(dp[i],dp[i]+right.size(),-1);
    }
    dp[0][0] = 0;
    for(int i=0;i<left.size();i++){
        for(int j=0;j<right.size();j++){
            if(dp[i][j]< 0) continue;
            if(left[i] > right[j]){
                dp[i][j] += right[j];
                dp[i][j+1] = max(dp[i][j+1],dp[i][j]);
            }
            else{
                dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]);
                dp[i+1][j] = max(dp[i+1][j],dp[i][j]);
            }
        }
    }
   for(int i=0;i<left.size();i++){
        answer = max(answer,max(dp[i][right.size()-1], dp[left.size()-1][i])); 
  }
    return answer;
}

+ 다른 분의 코드를 보니 훨씬 간단했다.

//dp 배열 모두 0으로 초기화 후
for(int i=0; i<=right.size(); i++) dp[0][i] = -1;

    for(int i=1; i<=left.size(); i++) {
        for(int j=1; j<=right.size(); j++) {
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]);
            if(dp[i][j-1] != -1 && left[i-1] > right[j-1]) dp[i][j] = dp[i][j-1] + right[j-1];
        }
    }

 return answer=dp[left.size()][right.size()];