[백준] 1633번: 최고의 팀 만들기 - java

문제설명

나의코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

import java.util.StringTokenizer;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int[] white;
	static int[] black;
	static int n = 0;
	static int[][][] dp;

	public static void main(String[] args) throws IOException {
		
		white = new int[1001];
		black = new int[1001];

		String s = "";
		while ((s = br.readLine()) != null) {
			n++;
			st = new StringTokenizer(s);
			white[n] = Integer.parseInt(st.nextToken());
			black[n] = Integer.parseInt(st.nextToken());		
		}
		

		// dp[i][w][b]
		// i번째 선수까지 선택했을 때 백팀 w명, 흑팀 b명일 때의 능력치 최댓값
		dp = new int[n+1][16][16]; 
		solution(n,15, 15);
		

		System.out.println(dp[n][15][15]);

	}
	
	static int solution(int i, int wIdx, int bIdx) {
		if (i==0)
			return 0;
		
		if (wIdx==0 && bIdx==0)
			return 0;
		
		int ans = dp[i][wIdx][bIdx];		
		
		if (ans != 0)
			return ans;
		
		// i번째 선수가 선택되지 않는다면
		ans = Math.max(ans, solution(i-1, wIdx, bIdx));
		
		// i번째 선수가 백팀에 들어간다면
		if (wIdx > 0)
			ans = Math.max(ans, solution(i-1, wIdx-1, bIdx)+white[i]);
		
		// i번째 선수가 흑팀에 들어간다면
		if (bIdx > 0)
			ans = Math.max(ans, solution(i-1, wIdx, bIdx-1)+black[i]);

		dp[i][wIdx][bIdx] = ans;
		return ans;
	}

}

 

 

dp, dfs 를 모두 쓴 문제이다.

dp[i][w][b] 는 i번째 선수까지 탐색했을 때 백팀 w명, 흑팀 b명을 골랐을 때의 능력치 최댓값 을 뜻한다.

white[i]는 i번째 선수가 백팀에 들어갈 때의 능력치, black[i]는 i번째 선수가 흑팀에 들어갈 때의 능력치이다.

 

 

DFS는 dp[n][15][15] 를 구하기 위해, dp[n][15][15]부터 시작해서 재귀를 통해 더 작은 부분 dp값들을 구하는 과정이다.

즉, dp[n][15][15]를 구하는 것이 DFS의 목적이란 것이다!!!

 

dp[n][15][15] (n번째 선수까지 모두 탐색했을 때, 백팀15명 흑팀15명을 골랐을 때의 능력치 최댓값) 가 될 수 있는 경우의 수는 3가지가 있다.

1. n번째 선수를 아예 선택하지 않는 경우 -> dp[n-1][15][15] 와 같을 것이다.
2. n번째 선수를 백팀으로 선택하는 경우 -> dp[n-1][14][15] + white[n] 
3. n번째 선수를 흑팀으로 선택하는 경우 -> dp[n-1][15][14] + black[n]

따라서 이 세가지 경우를 모두 탐색한 후에, 가장 큰 값이 dp[n][15][15]가 될 것이다.

 

=> 세 가지 경우를 구현한 코드이다. 

세 가지 경우에 따른 값들을 구하기 위해선 이전의 dp값이 필요하므로 재귀호출을 해야한다.

세 가지 경우값을 모두 구한 후에 최댓값이 dp[i][wIdx][bIdx] 가 되며, 해당값을 return 해준다.

 

 

DFS의 종료조건은 다음과 같다.

(i==0) => 모든 선수를 탐색한 경우. n부터 1번째 선수까지 모두 탐색한 경우이다. 

(wIdx == 0 && bIdx == 0) => 백팀에 들어간 선수가 0명, 흑팀에 들어간 선수가 0명인 경우이다. 이 경우엔 아무도 선택되지 않은 경우이므로, 0으로 리턴해준다.

 

 

 

문제를 이해하는 것이 조금 까다로울 수 있지만, (처음에 문제를 읽었을 땐 선수가 정확히 30명만 주어지는 줄 알았다...)

dp점화식을 잘 세우고, 0/1knapsack을 다룰 수 있다면 쉽게 풀릴 수 있는 문제였다.