백준 1285번 동전 뒤집기 - C++ 풀이

---

 

1. 각 행을 뒤집을지 여부를 고정한다.
2. 각 열을 뒤집을지 말지 여부를 tail 개수가 최소가 되도록 그리디 하게 정한다.

 

1. 각 행을 뒤집을지 여부를 고정한다.

 행이 최대 20개, 열이 최대 20개이므로 각 행과 열에 대해 뒤집을지 말지 여부를 결정하는 경우의 수는 2^40가지이다. 따라서 브루트 포스로는 시간 내에 해결할 수 없다. 먼저 행에 대해서만 뒤집을지 여부를 결정해주자. 경우의 수는 2^20가지로 줄어든다.

 

2. 각 열을 뒤집을지 말지 여부를 tail 개수가 최소가 되도록 그리디하게 정한다.

 행을 뒤집을지 말지 여부를 결정하고 나면, 이제 각 열의 뒤집을지 말지 여부는 그리디 하게 정할 수 있게 된다. 각 열끼리는 서로 영향을 미치지 않으므로, 각 열에 대해 뒤집는 경우와 뒤집지 않는 경우 중 더 tail이 적어지는 쪽을 택하면 된다. 이 과정의 시간 복잡도는 O(N^2)이 되므로, 최종 시간 복잡도는 O(N^2 * 2^N).

 

반응형

---

#include <iostream>

using namespace std;

int N;
string board[20];

// makeMinTail(row): 각 행을 뒤집을지 여부가 row로 주어졌을 때, 뒷면의 최소 개수
int makeMinTail(int row) {
    int ret = 0;
    
    // 각 열을 뒤집을지 말지 여부를 tail 개수가 최소가 되도록 정한다.
    for (int j=0; j<N; j++) {
        int headCnt = 0;
        
        for (int i=0; i<N; i++) {
            bool head = board[i][j] == 'H';
            if ((row & (1 << i)) != 0) head = !head;
            if (head) headCnt++;
        }
        
        ret += min(headCnt, N - headCnt);
    }
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    for (int i=0; i<N; i++) cin >> board[i];
    
    int ans = 987654321;
    for (int i=0; i<(1 << N); i++) {
        ans = min(ans, makeMinTail(i));
    }
    
    cout << ans;

    return 0;
}