그림 교환

백준 1029번: 그림 교환

아이디어

현재 그림을 가지고 있는 예술가를 X, 그 예술가가 그림을 구매한 가격을 Y, 지금까지 그림을 소유해봤던 예술가의 목록을 Z라 하고 cache[X][Y][Z]에 메모이제이션 ㄱㄱ

코드

#include <bits/stdc++.h>

using namespace std;

int N;
int arr[15][15];
int cache[15][10][1<<15];

int solve(int artist, int price, int visited) {
    if (visited == (1<<N)-1) {
        return 0;
    }

    int& ret = cache[artist][price][visited];
    if (ret != -1) return ret;

    ret = 0;
    for (int i = 0; i < N; i++) {
        if (price > arr[artist][i]) continue;
        if (visited&(1<<i)) continue;
        ret = max(ret, solve(i, arr[artist][i], visited|(1<<i))+1);
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < N; j++) {
            arr[i][j] = s[j]-'0';
        }
    }
    memset(cache, -1, sizeof(cache));
    cout << solve(0, 0, 1)+1;
    return 0;
}

여담

그림을 여러번 사도 되는 줄 알았는데 아니었다. 문제를 꼼꼼히 읽도록 하자.