백준 1633 최고의 팀 만들기

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

1633번: 최고의 팀 만들기

또다시 전형적인 다이나믹 프로그래밍 문제이다. 

문제들 중에는 매 번 또는 매 정점마다 어떠한 처리를 하며 나아갈 때 가장 마지막에 어떤 결과값을 갖는지를 찾는 형식의 문제가 많이 있다. 앞서 말한 '매 번 또는 매 정점마다' m가지의 처리를 할 수 있고 정점이 총 n개 있다면 마지막의 결과값은 무엇인지를 찾는 문제.

이런 문제에 대한 풀이를 나이브(naive)하게 생각해본다면 그 시간복잡도는 m의 n승이 된다. 

하지만 다이나믹 프로그래밍을 사용하면 보통 그 시간복잡도는 O(m^n) 에서 O(nm) 으로 바뀐다. 

당연한 얘기이지만 중복되는 연산을 걷어내기 때문이다. 중복되는 연산을 걷어내기 위해서는 서로 다른 조건으로 누적되는(또는 교차하는) 값들의 교차점에 어떠한 처리를 해줘야 한다. 다이나믹 프로그래밍에 대해 조금 정리해둔 글이 있다. 참고 부탁드린다.

 

이 문제에서 각 정점이란 '몇명의 백팀, 흑팀이 정해졌고 현재 몇번째 선수인지'가 된다.

즉 3차원 배열로 표현할 수 있게 된다. DP[i][white][black] (0<= white,black <=15)

각 선수 (최대 1000명) 곱하기 백팀 15 곱하기 흑팀 15 = 225,000의 최대 연산 횟수를 갖게 된다.

 

각 정점에서의 옵션은

1. 해당 선수를 선택할지 안할지
2. 백 팀으로 투입할지
3. 흑 팀으로 출전할지

이렇게 3가지가 된다. 

즉 3중 루프를 돌며, 매번 저 3가지의 옵션에 대한 처리를 해주면 된다.

 

<주요 내용>

다이나믹 프로그래밍 (DP)

 

<코드>

파이썬

이 문제에서는 몇 명의 선수가 명단에 있는지 먼저 알려주지 않는다. 무한입력을 어떻게 처리하는지 확인하자. for line in sys.stdin:...

import sys

info = []
for line in sys.stdin:info.append([int(e) for e in line.split()])
sz = len(info)
dp = [[[0 for _ in range(15+5)]for _ in range(15+5)]for _ in range(sz+1)]

for i in range(sz):
    for w in range(15+1):
        for b in range(15+1):
            if w+1 <= 15:
            	dp[i+1][w+1][b] = max(dp[i+1][w+1][b], dp[i][w][b]+info[i][0])
            if b+1 <= 15:
            	dp[i+1][w][b+1] = max(dp[i+1][w][b+1], dp[i][w][b]+info[i][1])
            dp[i+1][w][b] = max(dp[i+1][w][b], dp[i][w][b])

print(dp[sz][15][15])

 

C++

이 문제에서는 몇 명의 선수가 명단에 있는지 먼저 알려주지 않는다. 무한입력을 어떻게 처리하는지 확인하자. while(cin...)

#include <iostream>
using namespace std;
const int sz=1e3,tot=15+1;
int mx,temp1,temp2,dp[sz][tot][tot],p[sz][2];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int k=0;
    while(cin>>p[k][0]>>p[k][1])k++;
    dp[0][1][0]=p[0][0];
    dp[0][0][1]=p[0][1];
    for(int i=1;i<k;++i){
        for(int b=0;b<tot;++b){
            for(int w=0;w<tot;++w){
                temp1=0,temp2=0;
                if(b>0)temp1=dp[i-1][b-1][w]+p[i][0];
                if(w>0)temp2=dp[i-1][b][w-1]+p[i][1];
                dp[i][b][w]=max(max(temp1,temp2),dp[i-1][b][w]);
                if(b==tot-1&&w==tot-1)mx=max(mx,dp[i][b][w]);
            }
        }
    }
    cout<<mx;
    return 0;
}