백준 10835 - 카드게임

Java

10835 번 - 카드게임

문제

접근 방법

Top - down 방식으로 해결하되, DP를 통하여 왼쪽 카드와 오른쪽 카드를 버린 순서에 따라 기억하도록 하였다.
즉, dp[l][r]은 왼쪽에서 l개, 오른쪽에서 r개 버린 경우에 가장 점수가 높은 값을 저장 되어있다.

dp[0][0]에서 시작하여 왼쪽, 오른쪽 카드를 각각 버리는 경우에 따라 재귀함수를 호출하며,
오른쪽 카드를 버릴 때 마다, 해당 조합(dp[l][r])에 점수를 한다.

재귀함수를 호출 하였을 때, 이미 한번 방문한 조합이면(왼쪽 카드와 오른쪽 카드를 버린 개수) 함수를 재 방문하지 않고 지금까지 해당 조합에서 가장 점수가 높은 값(dp[l][r])을 리턴하도록 하면, 불필요한 방문을 줄일 수 있다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, result;
	static int[] aDummy,bDummy;
	static int[][] dp;
	public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk;
    n = stoi(br.readLine());

    aDummy = new int[n];
    bDummy = new int[n];
    dp = new int[n + 1][n + 1];

    stk = new StringTokenizer(br.readLine());
    for(int i = 0; i < n; i++) {
      aDummy[i] = stoi(stk.nextToken());
    }

    stk = new StringTokenizer(br.readLine());
    for(int i = 0; i < n; i++) {
      bDummy[i] = stoi(stk.nextToken());
    }

    for(int i = 0; i < n; i++) {
      Arrays.fill(dp[i], -1);
    }

    System.out.println(playGame(0,0));
    br.close();
	}

	static int playGame(int l, int r) {
		if(l == n || r == n)  // 카드가 더 이상 없을 시
			return dp[l][r] = 0;

		if(dp[l][r] != -1)    // 이미 한번 방문한 카드 조합이면
			return dp[l][r];


		if(aDummy[l] > bDummy[r]) {   // 왼쪽 카드 > 오른쪽 카드
			dp[l][r] = Math.max(dp[l][r], playGame(l, r + 1) + bDummy[r]);
		}

		dp[l][r] = Math.max(dp[l][r], playGame(l + 1, r + 1));    // 왼쪽 카드와 오른쪽 카드 동시에 버림
		dp[l][r] = Math.max(dp[l][r], playGame(l + 1, r));      // 왼쪽 카드만 버림


		return dp[l][r];
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

이외

이외의 방법으로 DFS로 풀수는 있다.
하지만 n의 최대가 2000이므로 시간초과를 발생 시킨다.

/*
문제이름
https://www.acmicpc.net/problem/10835

버리는 방법
1. 왼쪽 카드
2. 왼쪽, 오른쪽
3. 왼쪽 > 오른쪽 --> 오른쪽 버림 -> 점수 획득
*/

import java.util.*;
import java.io.*;

public class Main {
	static int n, result, maxSum;
	static int[] aDummy,bDummy;
	static int[][] dp;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());

    	aDummy = new int[n];
    	bDummy = new int[n];
    	dp = new int[n + 1][n + 1];

    	stk = new StringTokenizer(br.readLine());
    	for(int i = 0; i < n; i++) {
    		aDummy[i] = stoi(stk.nextToken());
    	}

    	stk = new StringTokenizer(br.readLine());
    	for(int i = 0; i < n; i++) {
    		bDummy[i] = stoi(stk.nextToken());
    	}

    	for(int i = 0; i < n; i++) {
    		Arrays.fill(dp[i], -1);
    	}

    	playDFSGame(0,0, 0);
    	System.out.println(maxSum);
    	br.close();
	}

	static void playDFSGame(int l, int r, int sum) {
		if(l == n || r == n) {
			maxSum = Math.max(maxSum, sum);
			return;
		}

		if(aDummy[l] > bDummy[r]) {
			playDFSGame(l, r + 1, sum + bDummy[r]);
		}

		playDFSGame(l + 1, r + 1, sum);
		playDFSGame(l + 1, r, sum);

	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점