백준 1285번 동전 뒤집기

🔒[문제 url]

https://www.acmicpc.net/problem/1285

🔑알고리즘

$i$번째 행을 뒤집은 후 $j$번째 열을 뒤집은 것과
$j$번째 열을 뒤집은 후 $i$번째 행을 뒤집은 것은 동일하다.
그러므로, 행을 뒤집은 모든 경우의 수에서 선택적으로 열을 뒤집자.

Backtracking을 이용해 조합을 구성하여 행을 뒤집은 후, $n$개의 열을 순회하며 뒤집을지 말지를 결정한 후 T의 갯수를 세어준다.

• 이때, 한 개의 열에 $k$개의 T가 있다면, min(k,n-k)만큼 T의 갯수가 늘어난다.
  • 예를 들어, 한 열이 위에서부터 아래로 H T T H H라면
    뒤집는 경우 T의 갯수는 3개, 뒤집지 않는 경우 T의 갯수는 2개가 되므로 min(3,2)인 2개가 추가되는 것이다.

🐾부분 코드

void Reverse(int k)
{
    for(int i = 0; i < n; i++)
        map[k][i] = (map[k][i] == 'H') ? 'T' : 'H';
}

<뒤집기 함수>
$k$번째 행을 뒤집는다.

void setAns()
{
    int cnt = 0;
    for(int i = 0; i < n; i++)
    {
        int colCnt = 0;
        for(int j = 0; j < n; j++)
        {
            if(map[j][i] == 'H')
                colCnt++;
        }
        cnt += min(colCnt,n-colCnt);
    }
    ans = min(ans,cnt);
}

<열 뒤집기 및 최소 T갯수 갱신 함수>
조합이 완성되면, $n$개의 열을 순회하며 T의 갯수를 세어준다.
이때 한 열에서 더해질 T의 갯수는 위에서 설명했듯 min(T갯수,n-T갯수)이다.

void Comb(int row)
{
    if(row == n)
    {
        setAns();
        return;
    }

    for(int i = row; i < n; i++)
    {
        Reverse(i);
        Comb(i+1);
        Reverse(i);//backtracking
    }
}

<조합 구성 함수>
Backtracking을 이용해 조합을 구성하여 뒤집을 행을 결정한다.
조합이 완성되면 setAns()를 호출한다.

🪄전체 코드

#include <iostream>

using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int n;
char map[21][21];
int ans = 0;

void INPUT()
{
    //IAMFAST
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int  j = 0; j < n; j++)
        {
            scanf("%1s", &map[i][j]);
            if(map[i][j] == 'T') ans++;
        }
}

void Reverse(int k)
{
    for(int i = 0; i < n; i++)
        map[k][i] = (map[k][i] == 'H') ? 'T' : 'H';
}

void setAns()
{
    int cnt = 0;
    for(int i = 0; i < n; i++)
    {
        int colCnt = 0;
        for(int j = 0; j < n; j++)
        {
            if(map[j][i] == 'H')
                colCnt++;
        }
        cnt += min(colCnt,n-colCnt);
    }
    ans = min(ans,cnt);
}

void Comb(int row)
{
    if(row == n)
    {
        setAns();
        return;
    }

    for(int i = row; i < n; i++)
    {
        Reverse(i);
        Comb(i+1);
        Reverse(i);//backtracking
    }
}

void SOLVE()
{
    Comb(0);
    cout << ans;
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

어려웠다.. 풀이를 보고 이해 못 할 정도의 난이도는 아니었지만, 결국 혼자 최적화된 풀이를 생각해내는 것은 실패했다. 예전부터 느꼈지만, 그리디가 dp보다도 난해하고 풀이를 증명하는 것또한 매우 힘들다. 그래도 코드는 상당히 깔끔하게 짠 듯하다.