백준 10835번: 카드게임

[백준 저지 링크]

 

dp (다이네믹 프로그래밍) 을 이용해서 풀었는데, 핵심은 한번 방문했던 인덱스를 생략하면서 모든 경우의 수에 max를 구하는 것입니다.

1) 왼쪽 카드만 버리기 2) 왼쪽 오른쪽 모두 버리기 3) 오른쪽 카드만 버리기 를 Top-down 방식으로 풀면 됩니다. (dfs로 풀면 메모리 초과로 에러 납니다.)

 

 

import java.io.*;
import java.util.StringTokenizer;
import java.util.Arrays;

class Main {
    static int strToInt(String s) { return Integer.parseInt(s);}

    static int n;
    static int[] left;
    static int[] right;
    static int[][] dp;

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

        n = strToInt(br.readLine());
        left = new int[n];
        right = new int[n];
        dp = new int[n][n];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++)
            left[i] = strToInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++)
            right[i] = strToInt(st.nextToken());

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

        System.out.println(solution(0, 0));
    }

    static int solution(int l, int r) {
        if(l == n || r == n)
            return 0;

        if(dp[l][r] != -1)
            return dp[l][r];

        dp[l][r] = Math.max(solution(l+1, r+1), solution(l+1, r));

        if(left[l] > right[r])
            dp[l][r] = Math.max(dp[l][r], solution(l, r+1) + right[r]);

        return dp[l][r];
    }
}