백트래킹 + dp로 풀었다.
왼쪽
1. 모든 투자가가 살아있는 상태에서 시작. 상태는 bitmask로 넘긴다
2. 파산 가능한 투자가를 하나씩 파산시켜보면서 dfs를 돈다.
3. depth == n/2까지 도달하면 dp table에 메모이제이션 하고 리턴한다.
오른쪽
1. i번째 투자가만 살아있는 상태에서 시작. 상태는 bitmask로 넘긴다
2. 현재 투자자 이전에 살아있었을 가능성이 있는 투자가를 살려보면서 dp를 돈다.
3. depth == n-n/2까지 도달하면 dp table을 보고 가능한지 여부를 판단한다.
파산 가능성을 볼 때 부채합산만 보면 바로바로 판단이 가능하다.
부채합산 s[] 를 계산하는법
n == 5, bitmask = 01100 이라면
d[0][0] d[0][1] d[0][2] d[0][3] d[0][4] : s'[0] = s[0] - d[0][1] - d[0][2]
d[1][0] d[1][1] d[1][2] d[1][3] d[1][4] : s'[1] = s[1] - d[1][1] - d[1][2]
d[2][0] d[2][1] d[2][2] d[2][3] d[2][4] : s'[2] = s[2] - d[2][1] - d[2][2]
d[3][0] d[3][1] d[3][2] d[3][3] d[3][4] : s'[3] = s[3] - d[3][1] - d[3][2]
d[4][0] d[4][1] d[4][2] d[4][3] d[4][4] : s'[4] = s[4] - d[4][1] - d[4][2]
인 상태이고 3번 투자가가 파산이 가능하다면 추가로 d[i][3]을 s'[i]에서 빼주면 된다.
그리고 bitmask를 참조하여 현재 살아있고 s[i] > 0 이면 파산 가능하므로 백트래킹을 타고 들어가면 된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 | #include <iostream> #include <algorithm> #include <memory.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; int t, tc, n; int a[20][20], cnt[20], p; ll s[20]; char d[1 << 20]; // bm = 살아남은 목록 char dfs1(int bm, int cnt) { if (cnt == n / 2) return d[bm] = 1; if (d[bm] != -1) return d[bm]; d[bm] = 0; for (int i = 0; i < n; ++i) { if (!(bm&(1 << i)) || s[i] <= 0 || d[bm ^ (1 << i)] != -1) continue; for (int j = 0; j < n; ++j) s[j] -= a[j][i]; if (dfs1(bm ^ (1 << i), cnt + 1) == 1) d[bm] = 1; for (int j = 0; j < n; ++j) s[j] += a[j][i]; } return d[bm]; } // bm = 살아남은 목록 char dfs2(int bm, int cnt) { char &ret = d[bm]; if (cnt == n - n / 2 || ret != -1) return ret; ret = 0; for (int i = 0; i < n; ++i) { if (bm&(1 << i) || s[i] <= 0 || d[bm ^ (1 << i)] == 0) continue; if (d[bm ^ (1 << i)] == 1) return ret = 1; for (int j = 0; j < n; ++j) s[j] += a[j][i]; if (dfs2(bm ^ (1 << i), cnt + 1) == 1) { for (int j = 0; j < n; ++j) s[j] -= a[j][i]; return ret = 1; } for (int j = 0; j < n; ++j) s[j] -= a[j][i]; } return ret; } int main(void) { ios::sync_with_stdio(false); cin.tie(0); cin >> t; for (tc = 1; tc <= t; ++tc) { memset(s, 0, sizeof(s)); cin >> n; memset(d, -1, sizeof(char)*(1 << n)); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) cin >> a[i][j], s[i] += a[i][j]; p = (1 << n) - 1; dfs1(p, 0); for (int i = 0; i < n; ++i) s[i] = 0; int ans = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) s[j] += a[j][i]; cnt[i] = dfs2((1 << i), 1); for (int j = 0; j < n; ++j) s[j] -= a[j][i]; if (cnt[i] > 0) ans++; } cout << "#" << tc << " " << ans << " "; for (int i = 0; i < n; ++i) { if (cnt[i] > 0) cout << i + 1 << " "; cnt[i] = 0; } cout << '\n'; } return 0; } | cs |
'SWEA' 카테고리의 다른 글
| 5548. 태양이의 캠프 조합 (0) | 2018.10.16 |
|---|---|
| 5789. 현주의 상자 바꾸기 (0) | 2018.10.16 |
| 1824. 혁진이의 프로그램 검증 (0) | 2018.10.08 |
| 2112. 보호 필름 (0) | 2018.10.08 |
| 4740. 밍이의 블록게임 (0) | 2018.10.07 |