코테 문제풀이 6일차

👑문제: [BOJ Gold5]

BOJ 1633 최고의 팀 만들기

풀이 시 고려해야 할 점

흑, 백, 아무것도 선택 안하는 것을 고려해서 dp로 만드는 게 꽤나 어려웠다.
앞과 어떤 관계가 있지? 라는 규칙을 생각하기가 어려웠는데, 이 점은 재귀로 해결 가능하였다.
dp[i][w][b] -> i 번째 index까지 white개수가 w이고 black개수가 b일때의 능력치 수
선택 안했을 때와 흑, 백을 선택했을 때의 경우의 수의 max값을 dp안에 넣어주어야 한다.

풀이 과정

package BOJ.DP;

import java.io.IOException;
import java.util.Scanner;
// 꼭 다시보기!!
public class G1633 {
    static int white[] = new int[1001];
    static int black[] = new int[1001];
    static int dp[][][] = new int[1001][16][16];
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int idx = 0;

        while(sc.hasNextInt()) {
            white[idx] = sc.nextInt();
            black[idx] = sc.nextInt();
            idx++;
        }
        System.out.println(makeTeam(15, 15, 0, idx));
    }

    static public int makeTeam(int w, int b, int idx, int num) {
        if(w == 0 && b == 0) return dp[idx][w][b];
        if(idx == num) return dp[idx][w][b];
        if(dp[idx][w][b] != 0) return dp[idx][w][b];

        //선택 안했을 경우
        int ans = makeTeam(w,b,idx+1,num);

        //선택 했을 경우
        if(w>0) ans = Math.max(ans, makeTeam(w-1,b,idx+1,num) + white[idx]);
        if(b>0) ans = Math.max(ans, makeTeam(w,b-1,idx+1,num) + black[idx]);
        dp[idx][w][b] = ans;

        return dp[idx][w][b];
    }
}

느낀점

꼭 다시 풀어야 할 문제!!