[백준 1633]최고의 팀 만들기(Java)

문제

https://www.acmicpc.net/problem/1633

풀이

DFS와 DP를 사용하였다.
DFS를 이용해 각각 i번째 사람이

1. 선택을 받지 않을 경우
2. 백팀이 될 경우
3. 청팀이 될 경우

로 나누어서 합을 구한다.

dp[i][w][b] : i번째 index에서 백팀이 w명, 청팀이 b명 존재할 때의 합

코드

import java.io.IOException;
import java.util.Scanner;

public class Main {

    public static int[] white;
    public static int[] black;
    public static int[][][] dp;
    public static void main(String args[]) throws IOException {
        Scanner scan = new Scanner(System.in);
        white = new int[1001];
        black = new int[1001];
        int index = 0;
        while(scan.hasNextInt()){
            white[index] = scan.nextInt();
            black[index] = scan.nextInt();

            index++;
        }
        dp = new int[1001][16][16];
        System.out.println(solution(0, 0, 0, index));

    }
    public static int solution(int i, int wIndex, int bIndex, int N){
        if(wIndex==15 && bIndex==15) return 0;
        if(i==N) return 0;

        if(dp[i][wIndex][bIndex]!=0) return dp[i][wIndex][bIndex];
        //선택 안했을 경우
        int ans = solution(i+1, wIndex, bIndex, N);
        //white
        if(wIndex<15) ans = Math.max(ans, solution(i+1, wIndex+1, bIndex,N)+white[i]);
        if(bIndex<15) ans = Math.max(ans, solution(i+1, wIndex, bIndex+1, N)+black[i]);
        //black
        dp[i][wIndex][bIndex] = ans;
        return dp[i][wIndex][bIndex];
    }
}