[BOJ] 최고의 팀 만들기 1633번 C++

 

문제

꿍 협회는 매년 세계체스대회에 나갈 팀을 만들고 있다. 팀은 흑으로 플레이하는 15명과 백으로 플레이하는 15명, 총 30명으로 이루어진다. 꿍 협회는 가능한 최고의 팀을 만들려고 하는데 각 플레이어의 흑,백 능력치는 각각 1부터 100까지의 정수로 주어진다. 대회가 진행되는 동안 플레이어는 흑, 백 중 한 가지만으로 참여를 해야하며 팀의 전체 능력치는 흑 플레이어의 능력치를 합한것과 백 플레이어의 능력치를 합한것을 모두 더한 값이다. 어떻게 하면 꿍 협회는 가능한 높은 능력치의 팀을 만들수 있을까.

입력

입력은 각 플레이어들의 능력치로 이루어진다. 각 줄은 공백으로 구분되는 두 개의 정수로 주어진다. 첫 번째 숫자는 해당 플레이어가 백으로 플레이를 할 때 능력치고 두 번째 숫자는 흑으로 플레이를 할 때의 능력치다. 최소한 30줄 이상이며 1000줄은 넘지 않는다.

 

출력

꿍 협회가 만들 수 있는 팀 중 가장 큰 능력치를 갖는 팀의 능력치를 출력한다.

 

접근 방식

 

dp[i][w][b]를 i번째 선수까지 고려했을 때 백팀을 w명, 흑팀을 b명 선택했을 때의 최대 점수라고 정의한다

따라서 만약 i번째 선수를 백팀에 넣는 경우 : dp[i][w][b] = max(dp[i][w][b] + dp[i-1][w-1][b] + 백팀 점수)

흑팀에 넣는 경우 : dp[i][w][b] = max(dp[i][w][b] + dp[i-1][w][b-1] + 흑팀 점수)

두 팀 모두 넣지 않는 경우 dp[i][w][b] = max(dp[i][w][b] , dp[i-1][w][b])

를 모두 고려하면 된다..

 

코드

#include<bits/stdc++.h>
using namespace std;

int dp[1003][17][17]; //i번째 선수까지 고려했을 때, 벡팀을 w명, 흑팀을 b명 선택했을 때의 최대 점수
int main() {
    int w,b;
    vector<pair<int,int>> v;
    while(cin>>w>>b) {
        v.push_back({w,b});
    }

    int n = v.size();
    memset(dp, 0, sizeof(dp));
    for(int i=0; i<n; i++) {
        int w_score = v[i].first;
        int b_score = v[i].second;

        for(int w=15; w>=0; w--) {
            for(int b=15; b>=0; b--) {
                if(w > 0){
                    dp[i+1][w][b] = max(dp[i+1][w][b], dp[i][w-1][b] + w_score);
                }
                if(b > 0) {
                    dp[i+1][w][b] = max(dp[i+1][w][b], dp[i][w][b-1] + b_score);
                }
                dp[i+1][w][b] = max(dp[i+1][w][b], dp[i][w][b]);
            }
        }

    }

    cout<<dp[n][15][15];

}