BOJ) 카드 게임

카드 게임

10835번: 카드게임

 

문제 조건

1. 왼쪽 카드만 통에 버릴 수도 있고 왼쪽과 오른쪽 카드를 둘 다 통에 버릴 수도 있다. (점수 X)

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

 

 

풀이

이 문제는 총 3번의 로직을 바꿔가며 풀었다.

 

1) 왼쪽과 오른쪽의 카드 모두 정렬해서, 왼쪽 카드의 최댓 값보다 작은 오른쪽 카드의 수를 더하기

여기서 간과한 점은, 무작위로 카드를 내는 것이 아니라, 이미 셔플되어있는 덱에서 카드를 꺼내는 경우기 때문에, 성립할 수 없다는 것을 알았다.

 

2) 투 포인터 활용

좌측의 카드를 역순으로 정렬하고있는 우선순위 큐를 선언하고, 오른쪽 카드가 큐에 담겨있는 최댓값보다 큰 경우, 두 수 모두 버리는 식으로 진행을 했다. 하지만, 이 방법 또한 항상 최대 스코어를 낼 수 없었다.

 

3) DP로 Memoization을 하고, DFS로 탐색

개인적으로 이 방법으로는 문제를 접근한 적이 많지 않아서 많이 어려웠다.

우선, DP를 특정 값으로 초기화 해주었다. (0보다 미만인 수는 모두 유효하다고 생각한다. 어차피 모든 카드는 자연수기 때문에, 0 이상인 값이라면 DP에서 활용할 수 있는 유효한 수가 된다. 다만, 특정 변수를 선언해주기 보다 이미 내장되어있는 Integer의 MIN_VALUE를 사용했다.)

 

이후, 왼쪽 카드의 시작과 오른쪽 카드의 시작부터 값을 탐색했다.

카드를 버리는 조건에 따라, 왼쪽 카드가 더 큰 경우에는 오른쪽에 적혀있는 카드의 숫자를 더하며 오른쪽 카드만 버려주었다. 같거나 오른쪽 카드가 더 큰 경우에는, 왼쪽 카드만 버리는 경우와, 둘 다 버리는 카드 중 더 큰 점수를 갖는 값을 더해주며 값을 갱신했다.

 

이 때, 이미 DP 값이 변동이 되어있는 상태라면, 다시 로직을 돌 필요가 없기 때문에, 사전에 초기화한 Integer.MIN_VALUE인지 확인해주며, 반복을 줄여주었다.

 

 

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class CardGame_10835 {
  static int[][] dp;
  static int[] left, right;
  static int n;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    n = Integer.parseInt(br.readLine());
    StringTokenizer st = new StringTokenizer(br.readLine());
    left = getCards(st);
    st = new StringTokenizer(br.readLine());
    right = getCards(st);

    br.close();
    solution();
  }

  private static void solution() {
    initDP();
    int answer =getMaxScore(0,0);
    System.out.println(answer);
  }

  private static void initDP() {
    dp = new int[n+1][n+1];
    for(int i=0; i<=n; i++) {
      Arrays.fill(dp[i], Integer.MIN_VALUE);
    }
  }

  private static int getMaxScore(int leftIndex, int rightIndex) {
    if(leftIndex >= n || rightIndex >= n) { // end of game
      return 0;
    }
    if(dp[leftIndex][rightIndex] != Integer.MIN_VALUE) { // memoization
      return dp[leftIndex][rightIndex];
    }
    dp[leftIndex][rightIndex] =0; // init

    if(left[leftIndex] > right[rightIndex]) {
      dp[leftIndex][rightIndex] += right[rightIndex] + getMaxScore(leftIndex, rightIndex+1); // drop only right card
    } else {
      dp[leftIndex][rightIndex] += Math.max(getMaxScore(leftIndex+1, rightIndex), getMaxScore(leftIndex+1,rightIndex+1));
      // max(drop only left, drop both left and right)
    }
    return dp[leftIndex][rightIndex];
  }

  private static int[] getCards(StringTokenizer st) {
    int[] cards = new int[n];
    for(int i=0; i<n; i++) {
      cards[i] = Integer.parseInt(st.nextToken());
    }
    return cards;
  }
}