[SWEA] 4613. 러시아 국기 같은 깃발

문제 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWQl9TIK8qoDFAXj&categoryId=AWQl9TIK8qoDFAXj&categoryType=CODE

SW Expert Academy

풀이

* 조합을 사용해서 백트래킹을 하며 모든 경우를 다 해본다. 

* 첫 행과 마지막 행은 흰색 / 빨간색으로 고정된다. 

2행부터 n-1 행까지의 조합을 구한다. 

* 조합을 구할 때 파란색이 반드시 포함되어야 한다. 

* W = 1 

B = 2

R = 3

으로 치환을 했다. 

색을 칠 할 때 이전의 행에 칠해진 색과 숫자가 같거나, 더 큰 숫자만 칠할 수 있다. 

예를 들어, 흰 -> 파 (O) / 파 -> 흰(X) 

파 -> 빨 (O) / 빨 -> 파(X)

 

* 이 특징을 이용해서 모든 경우를 전부 구하지 않고도 정답을 구할 수 있다. 

* chk[] => 이 배열에는 각 행마다 칠해질 색의 수가 지정된다. 

* n-1 행까지 칠해질 색이 정해졌다면 calc() 에서 정해진 색으로 바꾸기 위해 몇 개의 칸을 바꿔야 하는지 계산하여 반환한다.

 

 

?

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 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120

#include <iostream> #include <vector> #include <cstring> #define INF 987654321 using namespace std; //SWEA 4613. 러시아 국기 같은 깃발 //https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWQl9TIK8qoDFAXj&categoryId=AWQl9TIK8qoDFAXj&categoryType=CODE   int color[51][51]; int n, m; int ans = INF; int chk[51];   int calc() {     int ret = INF;       for (int i = 1; i < n - 1; i++)     {         if (chk[i] == 2)         {             ret = 0;             break;         }         //이 색으로 바꿔야 하낟.     }     if (!ret)     {         for (int i = 1; i < n - 1; i++)         {             int flag = chk[i];             for (int j = 0; j < m; j++)             {                 if (color[i][j] != flag)                 {                     ret++;                 }             }         }     }       return ret; } void dfs(int x, int c) {     if (x == n - 1)     {         int res = calc();         ans = min(ans, res);         return;     }       if (!chk[x])     {         int prev = chk[x - 1];         for (int j = prev; j <= 3; j++)         {             chk[x] = j;             dfs(x + 1, j);             chk[x] = 0;         }     } } int main() {       ios_base::sync_with_stdio(0);     cin.tie(0);       int t;     cin >> t;       for (int tc = 1; tc <= t; ++tc)     {         cin >> n >> m;           memset(color, 0, sizeof(color));         memset(chk, 0, sizeof(chk));         for (int i = 0; i < n; ++i)         {             for (int j = 0; j < m; ++j)             {                 char c;                 cin >> c;                 if (c == 'W')                     color[i][j] = 1;                 else if (c == 'B')                     color[i][j] = 2;                 else if (c == 'R')                     color[i][j] = 3;             }         }         //조합으로 구하기         ans = INF;         int res = 0;           for (int j = 0; j < m; ++j)         {             if (color[0][j] != 1)             {                   res++;                 color[0][j] = 1;             }             if (color[n - 1][j] != 3)             {                   res++;                 color[n - 1][j] = 3;             }         }           //1행부터 n-2행까지는 흰 -> 파 -> 빨 순서대로 와야 한다.         //각각 몇 개의 행을 차지하는 지는 조합으로 구한다.         dfs(1, 1);         cout << "#" << tc << " " << res + ans << '\n';     }       return 0; }