[백준] 1633번 - 최고의 팀 만들기 (C++) 문제 및 풀이

문제) 백준 - 동적 계획법 - 최고의 팀 만들기

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

1633번: 최고의 팀 만들기

 

동적 계획법을 통해 해결했습니다. solve(int idx, int b_cnt, int w_cnt) 함수는 idx번째 사람까지 고른 흑(b_cnt)과 백(w_cnt)을 골랐을 때, 능력치의 최댓값입니다. solve 함수 내에서 idx번째 사람을 뛰어넘거나 흑 플레이어로 추가하거나 백 플렉이어로 추가합니다.

 

C++ 소스코드)

	int solve(int idx, int b_cnt, int w_cnt){
	if(idx == N) return 0;
	if(b_cnt == 15 && w_cnt == 15) return 0;
	int &ret = cache[idx][b_cnt][w_cnt];
	if(ret != -1) return ret;
	// Skip
	ret = max(ret, solve(idx + 1, b_cnt, w_cnt));
	// White
	if(w_cnt < 15)
	ret = max(ret, solve(idx + 1, b_cnt, w_cnt + 1) + arr[idx][0]);
	// Black
	if(b_cnt < 15)
	ret = max(ret, solve(idx + 1, b_cnt + 1, w_cnt) + arr[idx][1]);
	return ret;
	}

view raw 1633.cpp hosted with ❤ by GitHub

Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/1633_%EC%B5%9C%EA%B3%A0%EC%9D%98%ED%8C%80%EB%A7%8C%EB%93%A4%EA%B8%B0.cpp

GitHub - Chocochip101/BOJ_Solution: BOJ Solutions