문제

문제 분석

Backtracking을 통해 모든 경우의 수를 조사하면 최적의 방법을 찾을 수 있다.
그러나 최악의 경우 시간복잡도가 O(N!)이므로 불가능하다.

문제를 자세히 살펴보면,
(1번,0원)->(3번,5원)->(다음 조사)
(1번, 0원)->(2번,4원)->(3번,5원)->(다음 조사)
subproblem이 반복되는 것을 볼 수 있으므로 DP로 풀어야 한다.
이때 축은 (사람, 가격) 이 된다.

그러나, 물건을 다시 사는 것을 방지해야하므로 구매 여부도 기록해야 한다.
이 부분은 bitmask로 처리할 수 있다.

따라서 최종적으로는 (사람, 가격, 구매여부(bitmask 값)) 을 축으로 하는 DP로 풀 수 있다.
또한, 필요 없는 칸이 많을 것이기에, tabulation보다는 memoization이 더 나을 것이다.

알고리즘

• Dynamic Programming
• Bitmask

자료구조

• 3차원 vector

결과

• 성공

#include <iostream>
#include <map>
#include <vector>
#include <string>

using namespace std;

const int MAX_N = 15;
const int CASE_NUM = (1<<15)-1; // 0(000 0000 0000 0000)
vector<vector<int>> srcToDstCostMat(MAX_N);
vector<vector<vector<int>>> memo( MAX_N, vector<vector<int>>(10, vector<int>(CASE_NUM, -1)) ); //NOTE: 최종 구매자, 가격, 루트 세 가지 생각해야하므로 3D

int visited = 0;
int N; // num of artist

int FindMaxNumBuyerRecursive( int src, int price, int depth );

int main( void )
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> N;

    for ( int r = 0; r < N; r++ ){
        string s;
        cin >> s;
        for ( int c = 0; c < N; c++ )
            srcToDstCostMat[r].push_back(s.at(c)-'0');
    }

    visited = 1;
    cout << FindMaxNumBuyerRecursive(0, 0, 1);

    return 0;
}

int FindMaxNumBuyerRecursive( int src, int price, int depth )
{
    // base Case
    if ( depth == N )
        return 1;

    // use memo
    if ( memo[src][price][visited] != -1 )
        return memo[src][price][visited];
    
    // Search
    int count = 0;
    const int savedVisited = visited;
    for ( int i = 0; i < N; i++ ){
        // Skip visited
        if ( (savedVisited & (1<<i)) != 0 )
            continue;

        // Search Rec
        if( srcToDstCostMat[src][i] >= price ){
            visited = (savedVisited | (1<<i));
            int rst = FindMaxNumBuyerRecursive( i, srcToDstCostMat[src][i], depth+1);
            if ( count < rst )
                count = rst;
        }
    }

    visited = savedVisited;
    memo[src][price][visited] = count+1;
    return memo[src][price][visited];
}

Other

DP를 사용할 때, 축의 개수를 잘 세팅하자.
덜 필요한지, 더 필요하진 않은 지 잘 생각해야 한다.