백준 1029, Bit DP
$N = 15$ 를 보고 bit dp를 생각은 했으나, 결국 dp 테이블을 만들지는 못했다.
이것도 오랫동안 못 풀었던 문제인데, 결국 답을 보고 알았다.
Design choice가 꽤 많은 문제 같아서 흥미로웠다.
DP 점화식을 세우는 세 가지 choice가 있는데,
bitmask로 15명 중 누가 샀는지 표시하는 것은 다 똑같다.
- $dp[\text{bitmask}][\text{last_ buyer}][\text{last_ cost}]$
앞에 bitmask에 표시 된 사람들이 샀을 때,
마지막 사람과 마지막으로 산 가격으로 테이블을 만들었다.
초기 값은 0으로 하고, 가능한 경우에만 1로 표시한다. 원본
- $dp[\text{bitmask}][\text{last_ buyer}][\text{next_ buyer}]$
앞에 bitmask에 표시 된 사람들이 샀을 때,
last buyer 에서 next buyer로 넘어갈 수 있는지 cost를 보고 결정한다. 링크
- $dp[\text{bitmask}][\text{last_ buyer}]$
테이블을 3차원이 아닌 2차원으로 줄여서 쓰는 방식이다.
아래 alex9801의 풀이를 참고한다.
이외 BOJ 질문 게시판을 봤을 때 priority queue로 푼 사람도 있는 것 같은데,
design choice가 매우 다양해서 재미있는 문제라고 생각한다.
Source Code
// https://www.acmicpc.net/problem/1029
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define MAXI 1000000000
#define cplx complex<double>
#define MOD 9901
const double PI = acos(-1);
const ll INF = INT_MAX / 4;
int N;
int price[20][20];
int dp[1 << 16][16][11];
int bitcount(int n) {
int cnt = 0;
for (int i = 0; i < 15; ++i) {
if (n & (1 << i)) ++cnt;
}
return cnt;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
int max_price = 0;
for (int i = 0; i < N; ++i) {
string s;
cin >> s;
for (int j = 0; j < N; ++j) {
price[i][j] = (int)(s[j] - '0');
// max_price = max(max_price, price[i][j]);
}
}
memset(dp, 0, sizeof(dp));
// get painting free
dp[1][0][0] = 1;
int ans = 1;
for (int state = 1; state < (1 << N); ++state) {
for (int j = 0; j < N; ++j) {
for (int cost = 0; cost <= 9; ++cost) {
if (dp[state][j][cost] == 0) continue;
ans = max(ans, bitcount(state));
if ((state & (1 << j))) {
for (int k = 0; k < N; ++k) {
if (state & (1 << k)) continue;
int next_state = state | (1 << k);
if (price[j][k] < cost) continue;
dp[next_state][k][price[j][k]] = 1;
}
}
}
}
}
printf("%d\n", ans);
return 0;
}
/*----------------------------------------------------------------
//alex9801's solution
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char ori[15][16];
int arr[14][14];
int mem[16384][14];
const int INF = 10;
int main()
{
int n, r, c, i, j, k;
scanf("%d", &n);
for(i = 0; i<n; i++)
scanf("%s", ori[i]);
n--;
for(i = 0; i<n; i++)
for(j = 0; j<n; j++)
arr[i][j] = ori[i+1][j+1] - '0';
for(i = 1; i < (1<<n); i++)
for(j = 0; j<n; j++)
mem[i][j] = INF;
for(i = 0; i<n; i++)
mem[1<<i][i] = ori[0][i+1] - '0';
r = 1;
for(i = 1; i < (1<<n); i++)
{
for(j = 0; j<n; j++)
{
if(mem[i][j] == INF)
continue;
c = n+1;
for(k = 0; k<n; k++)
{
if(i & (1<<k))
continue;
c--;
if(arr[j][k] >= mem[i][j])
mem[i | (1<<k)][k] = std::min(mem[i | (1<<k)][k], arr[j][k]);
}
r = std::max(r, c);
}
}
printf("%d", r);
return 0;
}
*/
// MY WA
// int N;
// int price[15][15];
// int adj[15][15];
// bool visited[15];
// int dfs(int start){
// int max_step = 0;
// visited[start] = true;
// for (int i = 1; i < N;++i){
// if(adj[start][i] == 0) continue;
// if (visited[i]) continue;
// visited[i] = true;
// max_step = max(max_step, dfs(i));
// }
// visited[start] = false;
// return max_step + 1;
// }
// int main() {
//
// //ifstream cin; cin.open("input.txt");
// cin >> N;
// for (int i = 1; i <= N;++i){
// for (int j = 1; j <= N;++j){
// cin >> price[i][j];
// }
// }
// memset(adj, 0, sizeof(adj));
// for (int i = 1; i < N;++i){
// if (i == 1) continue;
// adj[1][i] = 1;
// }
// for (int k = 1; k <= N; ++k) {
// for (int i = 1; i <= N; ++i) {
// for (int j = 1; j <= N; ++j) {
// if(adj[i][k] == 1
// && adj[k][j] == 1
// && price[i][k] <= price[k][j]){
// adj[i][j] = 1;
// }
// }
// }
// }
// memset(visited, 0 , sizeof(visited));
// int ret = dfs(1);
// printf("%d\n", ret);
// return 0;
// }