[Algorithm]Baekjoon 1029번 :: 그림교환

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

 

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
int costInfo[16][16] = { 0 };
int n;
int dp[15][1 << 15][10] = { 0 };
 
 
int DFS(int index, int visited, int cost)
{
    int& result = dp[index][visited][cost];
    
    if (result != -1) return result;
 
    result = 1;
 
    for (int i = 1; i < n; ++i)
    {
        if (visited & (1 << i)) continue;
        if (costInfo[index][i] < cost) continue;
 
        result = max(result, DFS(i, visited | (1 << i), costInfo[index][i]) + 1);
    }
    
    return result;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        string s;
        cin >> s;
 
        for (int j = 0; j < s.size(); ++j)
        {
            costInfo[i][j] = s[j] - '0';
        }
    }
 
    memset(dp, -1, sizeof(dp));
    
    cout << DFS(0, 1, 0);
}

 

 

외판원문제가 생각나는 문제이다.

다만, 이 문제에서는 각 경로를 이동하는데에 조건이 달려있다. 이전에 구입한가격 '이상'으로만 팔 수 있다는 것이다.

그렇기 때문에 dp를 3차원테이블로 해야한다.

이것 말고는 크게 유의할점은 없어보인다.