[DP] BOJ 1029 그림 교환

문제 링크 : www.acmicpc.net/problem/1029

1029번: 그림 교환

이 문제를 DP로 풀기 위해 필요한 정보는 다음과 같다.

① 현재까지 그림을 산 사람들에 대한 정보 (한번 그림을 산 사람은 다시 살 수 없으므로)

② 마지막으로 그림을 산 사람 (다음에 살 사람의 가격은 마지막으로 산 사람에 의해 정해진다.)

③ 마지막으로 팔았을 때 그림의 가격 (다음에 살 사람은 이 가격 이상으로 사야 하기 때문)

 

따라서, 이 3가지 정보를 담은 3차원 dp 배열을 통해 문제를 해결한다.

N의 범위가 15로 매우 작기 때문에, 현재까지 그림을 산 사람은 비트마스크로 표현할 수 있다.

비트마스크로 표현한 그림을 구매한 사람들에 대한 정보를 통해 그림을 산 사람의 수를 구할 수 있으므로, dp 배열의 값은 단지 도달할 수 있는지에 대한 여부만 나타내었다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
 
using namespace std;
typedef pair<int, int> p;
 
int n, max_cost;
int cost[16][16];
int dp[1 << 16][16][10];
int answer = 1;
 
int get_answer(int state) {
    int div = pow(2.0, 15);
    int ret = 0;
 
    while (div > 0) {
        if (state >= div) {
            state -= div;
            ret++;
        }
        div /= 2;
    }
 
    return ret;
}
 
void set_dp() {
    dp[1][1][0] = 1;
 
    for (int i = 1; i < (1 << n); i++) {
        int state = i;
 
        //state의 j번째 비트에 대해 (j는 마지막으로 산 사람의 번호를 의미)
        for (int j = 0; j < n; j++) {
            //최고 가격이 c인 경우
            for (int c = 0; c <= max_cost; c++) {
                //도달할 수 없는 경우는 무시
                if (dp[i][j + 1][c] == 0) continue;
                answer = max(answer, get_answer(i));
 
                //현재 state에서 그림을 산 사람에 대해서만
                if (state & (1 << j)) {
                    //그림을 산 j번 사람에 대해 그림을 사지 않은 k번째 사람을 계산
                    for (int k = 0; k < n; k++) {
                        if (state & (1 << k)) continue;
                        int newstate = state | (1 << k);
                        if (cost[j + 1][k + 1] < c) continue;
                        dp[newstate][k + 1][cost[j + 1][k + 1]] = 1;
                    }
                }
            }
        }
    }
}
 
void init() {
    string input;
    cin >> n;
    
    for (int i = 1; i <= n; i++) {
        cin >> input;
        for (int j = 1; j <= n; j++) {
            cost[i][j] = input[j - 1] - '0';
            max_cost = max(max_cost, cost[i][j]);
        }
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    set_dp();
    printf("%d\n", answer);
 
    return 0;
}