[BOJ/DP] 1029 그림교환

BOJ 1029 그림교환 https://www.acmicpc.net/problem/1029

 

이 문제 처음부터 너무 쉽게 생각하고 접근한 것 같다....

 

1. 그림을 팔 때, 그림을 산 가격 보다 크거나 같은 가격으로 팔아야 한다.

2. 같은 그림을 두번 이상 사는 것은 불가능하다. 

위의 조건 두개 만 보고 여기에 대해서만 조건을 걸어서 DFS 탐색으로 가지치기 대충 하면 맞을 줄 알았는데..;; 여지 없이 시간초과로 FAIL이 난다...

 

N 범위도 15까지밖에 안되서 쉽게 끝날 줄 알았는데... 

근데 이게 조건이 하나 더 있다는걸 나중에 알았다는... 입력 조건에 금액에 대한 범위가 지정되어 있어서 거기에 대해서도 방문 조건을 걸어줘야 했다.

 

아마 금액에 대한 방문 조건을 걸지 않아서 시간 초과가 난게 아닌가...

 

이 문제에서 고려해야 하는 조건은 

1. 지금까지 방문한 곳에대한 정보

2. 그때 방문하는 아티스트에 대한 정보

3. 그때의 비용

3가지로 볼 수 있다.

 

이 정보들을 이용하기 위해서 DP를 이용하기로함..

 

DP는 DP[1 << MAXN][MAXN][MAX_PRICE]로 정의 하는데 

[1 << MAXN]는 최대 15명의 아티스트를 방문했던 상태들을 비트마스크로 만들어서 표현

[MAXN]는 어떤 아티스트를 방문했는지의 상태

[MAX_PRICE]는 방문한는 순간의 금액을 표현함

 

문제에 대한 코드는 아래와 같음.

#include <stdio.h>
#define MAXN 15
#define MAX_PRICE 10
int cost[MAXN][MAXN];
int dp[1 << MAXN][MAXN][MAX_PRICE] = { 0, }; 
int n;
int solve(int visit, int from, int c, int d) {
    int& ret = dp[visit][from][c];
    if (ret != 0) return ret;
    ret = d;
 
    for (int to = 0; to < n; ++to) {
        if (to == from) continue;
        if (c > cost[from][to]) continue;
        if (visit & (1 << to)) continue;
        int tmp = solve((visit | (1 << to)), to, cost[from][to], d + 1);
        ret = ret > tmp ? ret : tmp;
    }
 
    return ret;
}

int main() {

    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j)
            scanf(" %1d", &cost[i][j]);
    }
    printf("%d\n", solve((1 << 0), 0, 0, 1));
 
    return 0;
}

아무래도 너무 오랜만에 문제를 푼것같은느낌이 든다..

우선 이 문제에서 핵심은 DP + BITMASK인듯함...