[백준 1633번] 최고의 팀 만들기 (C++)

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

 

1000개 중 30개를 적절히 구하는 것은 1000개중 30개를 뽑는 모든 연산을 진행해야한다. 1000 combination 30 = 2429608192173745103270389838576750719302222606198631438800 이다.

 

미친시간이 걸리기 때문에 완전탐색은 불가능하다. 

 

탐욕법 (Greedy)

그디리하게 접근해보자. 문제 조건처럼 총 30개를 선택하는 건 어려우니 백2, 흑2 총 4팀을 뽑는다고 가정하자.

(10, 20), (30, 400), (5, 1000), (100, 10), (40, 40), (15, 30)

 

이렇게 들어올 때, 흑으로 정렬한다.

 

(100, 10), (40, 400), (30, 40), (15, 30), (10, 20), (5, 1000)

 

그리고 만약 백 > 흑 이면 백으로 세팅, 아니면 흑으로 세팅해보자.

 

백: 100

흑: 400, 40

 

그리고 백이 부족하므로 가능한 것 중 가장 큰 백을 선택하면 30이므로 탐욕법을 쓰면 570이 나온다. 그러나 모두 보다시피 이것은 정답이 아니다. 탐욕법은 두가지 문제점이 있다. 위처럼 백을 탐욕적으로 하면 흑을 최대로 만들 수 없으며 흑백이 모두 같은 전투력이라면 이것을 어느쪽에 배치해줘야할지 알 수 없다. 

 

동적계획법 (Dynamic Programming)

그렇다면 동적계획법은 어떨까? 모든 값을 체크하지 않고 메모이제이션을 통해 최적화할 수 있을까? 동적계획법에서 가장 어려운 점은 몇차원으로 잡을 것인가? 이 DP를 어떻게 정의할 것인가? 두가지를 정하는 근거를 찾는것이다.

 

들어오는 순서대로 생각할 때 선택지는 총 3가지이다.

1. 백으로 선발한다.

2. 흑으로 선발한다.

3. 선발하지 않는다.

 

그렇다면 DP[i][j][k] = " i번째 선수까지 봤을 때, 백 플레이어 j명, 흑 플레이어 k명을 뽑았을 때 최대 전투력 " 으로 정의할 수 있을 것이다. 

 

위에서 선택지를 좀 더 자세히 정의해보자. 현재 i 번 선수 영입을 고려하고 있다고 가정하자. 그렇다면 i - 1 번째까지 고려했을 때와 비교하게 될 것이다. 

 

1. j 번째 백으로 선발 => 전투력 = j - 1 명의 백, k 명의 흑을 선발 했을 때 + 현재 백 전투력

2. k 번째 흑으로 선발 => 전투력 = j 명의 백, k - 1명의 흑을 선발 했을 때 + 현재 흑 전투력

3. 전투력 = 이전 전투력

 

그리고 이번 연산에서 가장 최고의 전투력을 갖추는 선택을 해야하므로 3개의 조건 중 가장 큰 값을 메모이제이션한다.

 

이것을 코드로 바꿔보자.

DP[i][j][k] = max(DP[i - 1][j][k], max(DP[i - 1][j - 1[k] + WHITE , DP[i - 1][j[k - 1] + BLACK))

 

이렇게 진행하면 결국 1000개의 입력 중 흑 15개, 백 15개만 보면 되니까 1000 * 15 * 15 로 아주 짧은 시간내에 문제를 해결할 수 있다. 이것을 코드로 만들어보면 다음과 같다. 

#include<iostream>
#include<vector>
using namespace std;

int dp[1001][16][16];

vector<pair<int, int>> vec;

int main() {
	int n, m;
 
    while(cin >> n >> m) vec.push_back({n,m});

    int answer = 0;

    dp[0][0][1] = vec[0].second;
    dp[0][1][0] = vec[0].first;

    for(int i = 1; i < vec.size(); i++){
        int black = vec[i].second;
        int white = vec[i].first;
        for(int j = 0; j <= 15; j++){
            for(int k = 0; k <= 15; k++){
                int val1 = 0, val2 = 0;

                if(j > 0) 
                    val1 = dp[i - 1][j - 1][k] + white; // 흑 영입
                if(k > 0) 
                    val2 = dp[i - 1][j][k - 1] + black; // 백 영입

                dp[i][j][k] = max(max(val1, val2), dp[i - 1][j][k]);
            }
        }
    }

    cout << dp[vec.size() - 1][15][15] << '\n';
}