#백준_10835 카드게임 - Java 자바

# 유형 : 재귀, DP

# 난이도 : 실버 1

# 1) 언제든지 왼쪽 카드를 버리거나 왼쪽,오른쪽 다 버리는 경우

   2) 왼쪽 값이 오른쪽 값보다 클 때 오른쪽 카드를 버리는 경우 로 나누어서 재귀함수로 구하면 된다.

 

package bj;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p10835 {
    static int N;
    static int A[],B[], dp[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        A = new int[N];
        B = new int[N];
        dp = new int[N][N];
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++)
                dp[i][j] = -1;
        }
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++)
            A[i] = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++)
            B[i] = Integer.parseInt(st.nextToken());
        
        System.out.println(solve(0,0));
    }
    
//    언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다.
//    오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.
//    (1)과 (2)의 규칙에 따라 게임을 진행하다가 어느 쪽 더미든 남은 카드가 없다면 게임이 끝나며 그때까지 얻은 점수의 합이 최종 점수가 된다. 
    public static int solve(int left, int right) {
        if(left>=N || right>=N)
            return 0;
        
        if(dp[left][right] != -1)
            return dp[left][right];
        
        //언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다.
        dp[left][right] = Math.max(solve(left+1, right), solve(left+1, right+1));
        
        //오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.
        if(A[left] > B[right])
            dp[left][right] = Math.max(dp[left][right], B[right] + solve(left, right+1));
        
        return dp[left][right];
    }
}