#include <stdio.h> #include <iostream> using namespace std; const int DSIZE = 13; const int WSIZE = 20; int D, W, K; int film[DSIZE][WSIZE]; int minChemicalCnt; int chemical[DSIZE]; void solve(int curD, int chemicalCnt, int prevContinuum[WSIZE], int prevMaxContinuum[WSIZE]) { if (chemicalCnt >= minChemicalCnt) return; if (curD == D) { bool isSatisfied = true; for (int i = 0; i < W; i++) { if (prevMaxContinuum[i] < K) { isSatisfied = false; break; } } if (isSatisfied && chemicalCnt < minChemicalCnt) minChemicalCnt = chemicalCnt; return; } int continuum[WSIZE], maxContinuum[WSIZE]; int prev, cur; for (int i = 2; i >= 0; i--) { chemical[curD] = i; for (int j = 0; j < W; j++) { cur = chemical[curD] == 2 ? film[curD][j] : chemical[curD]; prev = chemical[curD - 1] == 2 ? film[curD - 1][j] : chemical[curD - 1]; continuum[j] = cur == prev ? prevContinuum[j] + 1 : 1; if (continuum[j] > prevMaxContinuum[j]) maxContinuum[j] = continuum[j]; else maxContinuum[j] = prevMaxContinuum[j]; } solve(curD + 1, chemicalCnt + (i == 2 ? 0 : 1), continuum, maxContinuum); } } int main() { int test_case; cin >> test_case; for (int tc = 1; tc <= test_case; tc++) { cin >> D >> W >> K; for (int i = 0; i < D; i++) { for (int j = 0; j < W; j++) { cin >> film[i][j]; } } minChemicalCnt = K; int continuum[WSIZE], maxContinuum[WSIZE]; for (int i = 0; i < W; i++) continuum[i] = maxContinuum[i] = 1; chemical[0] = 2; solve(1, 0, continuum, maxContinuum); chemical[0] = 0; solve(1, 1, continuum, maxContinuum); chemical[0] = 1; solve(1, 1, continuum, maxContinuum); cout << "#" << tc << " " << minChemicalCnt << endl; } return 0; } |
보호필름 문제를 보면 재귀와 순열이 모두 들어갑니다. 먼저 내가 생각 한 아이디도 맞으나, 2진수를 만들지 않고, 포문으로 들어가서 해결하는 것으로 풀이가 가능합니다. 3가지 경우의 수가 있으므로, 이것에 대해서 모두 풀어주는 것입니다. 단, 처음에 들어가는 것은 입력을 넣어주어야 합니다. 그리고 끝나는 리턴조건도 중요하고 dfs 안에 있는 continuum 과 maxContinuum 의 변수를 저곳에 새로 넣어주는 것도 엄청 납니다. 그리고 가져가는 변수들을 보면, continuum 을 저기에 선언해주는 이유가 무엇일까? 다른 곳에 하면 안되는 것인가? 한번 해보도록 하겠습니다. 안됩니다. 안되는 이유가 저기서 변경되는 것인데, 다시 돌아오려면 값이 저장되어 있어야 합니다. cur, prev 의 경우에는 새로 불러주기 때문에 상관이 없을 것 같은데, 그리고 끝에 까지 갔다가 하나씩 돌아오는 것을 하려면 저렇게 포문을 넣고, dfs 를 돌리면서 리턴 조건을 넣어주면 되는구나. 리턴조건에 대해서 다시 찾아보도록 하겠습니다. cur == D 이면 이것입니다. 오께이 그리고 cehmicalCnt 도 살펴보도록 합니다. 그리고 케미칼이 사용된것이 2개이상이면 리턴을 하도록 합니다. 리턴조건이 단순하게 길이만 있습니다. 2개가 있습니다. 하나는 변경 갯수, 하나는 모두 검사를 마쳤을때, 그 아래는 컨티넘, 맥스컨니넘을 저기에서 선언하는 것이 신의 한수 인 것 같습니다. 저렇게 짜면 아까 트리가 만들어지는 구나, 오께이 계산하는 방법에 대해서 다시 찾아보도록 하겠습니다. ● |