/* 0905 보호 필름 스스로 풀어보기 */ #include <iostream> #include <algorithm> using namespace std; #define SIZED 13 #define SIZEW 20 int map[SIZED][SIZEW]; int medical[SIZED]; int D, W, K; int ans; int con[SIZEW]; int maxCon[SIZEW]; void problemIn() { cin >> D >> W >> K; for (int i = 0; i < D; i++) { for (int j = 0; j < W; j++) { cin >> map[i][j]; } } } void dfs(int curD, int medCnt, int prevCon[SIZEW], int prevMaxCon[SIZEW]) {
if (medCnt >= K) { return; } if (curD == D) { bool isSatisified = true; for (int i = 0; i < W; i++) { if (prevMaxCon[i] < K) { isSatisified = false; break; } } if (isSatisified && medCnt < K) { ans = min(ans, medCnt); } return; } int con[SIZEW], maxCon[SIZEW]; int cur, prev; for (int i = 2; i >= 0; i--) { medical[curD] = i; // 2 2 for (int j = 0; j < W; j++) { cur = medical[curD] == 2 ? map[curD][j] : medical[curD]; prev = medical[curD - 1] == 2 ? map[curD - 1][j] : medical[curD-1]; con[j] = cur == prev ? prevCon[j] + 1 : 1; if (con[j] > prevMaxCon[j]) maxCon[j] = con[j]; else maxCon[j] = prevMaxCon[j]; } dfs(curD + 1, (i == 2) ? medCnt : medCnt + 1, con, maxCon); } } void solve() { for (int i = 0; i < W; i++) { con[i] = 1; maxCon[i] = 1; } medical[0] = 2; dfs(1, 0, con, maxCon);
medical[0] = 0; dfs(1, 1, con, maxCon); medical[0] = 1; dfs(1, 1, con, maxCon); } int main() { int T; cin >> T; for (int tc = 1; tc <= T; tc++) { problemIn(); ans = K; solve();
cout << "#" << tc << " " << ans << endl; ans = K; } return 0; } |
시간복잡도를 계산하고 나서, 풀었어야 합니다. 완전탐색중에서도 순열이기 때문에, 조합보다 더 탐색해야합니다. 그러기 위해서는 dfs 안에 for 문을 넣어서 하나씩 넣으면 됩니다. 단, 한가지 차이점이 처음 들어갈때입니다. dfs 를 할 때, 처음 들어가는 것과 나오는 리턴문의 조건이 중요합니다. 그리고 con, maxcon 을 dfs 안에서 설정함으로써, 새로운 것으로 받을 수 있고, preCon, preMaxCon 을 사용함으로써 기존의 값들을 저장해서 계속해서 사용가능합니다. 그리고 아이디어가 SIZED 1차원 행렬을 만들어서, 들어가는 약물을 계산한 것입니다. 이렇게 하면 dfs 를 하면서 기존에 계산했던 값들을 계속해서 사용할 수 있습니다. 그래도 어떻게 풀었네요. 방법에 대해서 알았으니, 다음에도 이런 유형이 나오면 당황하지 않고 차분히 풀도록 하세요. 그리고 새로운 배열이 들어오면, 초기화를 반드시 해주어야 합니다. 그러므로 새로운 배열에 대한 값이 들어갈때, 변동되지 않는 값에도 값을 넣어주도록 하겠습니다. |