링크

10835 카드게임

문제

풀이

top-down을 통해서 풀었다. 처음에 0으로 셋팅하고 풀었는데 0으로 셋팅하고 풀었었다.
0으로 dp배열을 초기화하고 푸니까 문제가 생겼던 것이 0의 값이 나와서 dp 배열에 저장을 했는데 저장을 안한것처럼 계산이 되면서 다시 계산해버리는 문제가 생겼다. 그래서 -1로 쭉 초기화하고 풀었더니 64점에서 100점으로 통과했다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.nio.Buffer;
import java.sql.Array;
import java.util.*;

public class Main {
    public static int n;
    public static int[][] dp;
    public static int[] leftDummy;
    public static int[] rightDummy;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());

        leftDummy = new int[n];
        rightDummy = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++) {
            leftDummy[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++) {
            rightDummy[i] = Integer.parseInt(st.nextToken());
        }

        dp = new int[n][n];

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

//		for(int i=0;i<n;i++) {
//			System.out.println(Arrays.toString(dp[i]));
//		}

    }

    public static int recur(int dept, int right) {

        //벗어나는 경우
        if(dept >= n || right >= n) {
            return 0;
        }


        if(dp[dept][right] != -1) {
            return dp[dept][right];
        }

        //왼쪽 카드만 통에 버리기
        int case1 = -1;
//		if(dept < n)
        case1 = recur(dept+1, right);


        //오른쪽 카드와 왼쪽 카드 둘다 버리기
        int case2 = -1;
//		if(dept < n && right < n)
        case2 = recur(dept+1, right+1);


        //오른쪽 카드만 버리기
        int case3 = -1;
//		if(leftDummy[dept] > rightDummy[right] && right < n)
        if(leftDummy[dept] > rightDummy[right])
            case3 = recur(dept, right+1) + rightDummy[right];


        if(case1 == -1 && case2 == -1 && case3 == -1) return 0;

        dp[dept][right] = Math.max(case1, Math.max(case2, case3));

        return dp[dept][right];
    }


}