백준 1029번 그림 교환 - C++ 풀이

---

 

1. dp(curr, price, mask) = 현재 curr이 price원에 그림을 가지고 있고 지금까지 그림을 산 사람들이 mask일 때, 더 그림을 소유할 수 있는 사람 수의 최댓값
2. dp(curr, price, mask) = max(1, 1 + dp(next, nextPrice, newMask))

 

1. dp(curr, price, mask) = 현재 curr이 price원에 그림을 가지고 있고 지금까지 그림을 산 사람들이 mask일 때, 더 그림을 소유할 수 있는 사람 수의 최댓값

 dp(curr, price, mask)를 위와 같이 정의하자. 사람은 최대 15명, 가격은 최대 9원이므로 총 구해야 하는 dp값은 15*10*(2^15) 개.

 

2. dp(curr, price, mask) = max(1, 1 + dp(next, nextPrice, newMask))

 이제 curr번 사람에게서 그림을 살 다음 사람을 골라야 한다. 모든 사람을 순회하면서 아직 그림을 산 이력이 없고, price원보다 높거나 같은 가격에 그림을 살 수 있는 사람들을 모두 고려해준다. 각 dp값을 구하기 위한 시간 복잡도는 O(N). 따라서 총 시간복잡도는 O(10*N*2^N)

 

반응형

---

#include <iostream>
#include <cstring>

using namespace std;

int N;
int sell[16][16];
int cache[16][10][1 << 16];

// dp(curr, price, mask)
// 현재 curr이 price원에 그림을 가지고 있고
// 지금까지 그림을 산 사람들이 mask일 때,
// 더 그림을 소유할 수 있는 사람 수의 최대값
int dp(int curr, int price, int mask) {
    int& ret = cache[curr][price][mask];
    if (ret != -1) return ret;
    
    ret = 1;
    for (int next=1; next<=N; next++) {
        if (curr == next) continue;
        if ((mask & (1 << next)) != 0) continue;
        if (sell[curr][next] < price) continue;
        
        ret = max(ret, 1 + dp(next, sell[curr][next], mask|(1 << next)));
    }
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    memset(cache, -1, sizeof(cache));
    
    cin >> N;
    for (int i=1; i<=N; i++) {
        string temp;
        cin >> temp;
        for (int j=1; j<=N; j++) {
            sell[i][j] = temp[j-1] - '0';
        }
    }
    
    cout << dp(1, 0, 1 << 1);

    return 0;
}