[1029] 그림 교환

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

처음에 dfs로 방문체크를 하면서 cost가 크거나 같으면 이동하는 식으로 해서 해결해보려고 했으나

65프로에서 시간초과가 뜨더군요.

제한시간이 2초인데

dfs로 하면 최악의 경우 15!의 시간이 걸리기 때문에 해결할 수 없었습니다.

그래서 dp를 이용해야 했는데..

방문한 곳의 상태가 필요했기 때문에 비트마스크를 사용했습니다.

제 dp의 정의는

dp[1 << 15][15][10] : 방문상태, 아티스트 번호, 비용으로 정의했습니다.

아래는 코드입니다.

f함수의 매개변수는 방문상태, 아티스트 번호, 코스트, 깊이 입니다.

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
 
#define ll long long
#define MAX_SIZE 15
#define INF 987654321
#define MOD 1000000
using namespace std;
 
int dp[1 << MAX_SIZE][MAX_SIZE][10]; //state, artistNumber, cost
int cost[MAX_SIZE][MAX_SIZE];
int n;
 
int f(int state, int artist, int c, int d) {
    int &ret = dp[state][artist][c];
    if (ret != 0) return ret;
    ret = d;
 
    for (int i = 0; i < n; i++) {
        if (state & (1 << i) || cost[artist][i] < c) continue;
        ret = max(ret, f(state | (1 << i), i, cost[artist][i], d + 1));
    }
    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", f(1, 0, 0, 1));
    
    return 0;
}