문제 노트/정올

동전 뒤집기( BOJ 1285 )

ivymso 2022. 8. 3. 23:03

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

 

1285번: 동전 뒤집기

첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위

www.acmicpc.net

 

문제 파악하기

2006년 정보올림피아드 고등문제의 small 버전 문제입니다. N*N개의 동전을 뒤집어서 동전의 뒷면(T)이 최소로 보이게 만들었을 때, N*N개의 동전 중 뒷면(T)의 개수를 구하는 문제입니다. 동전은 행 또는 열을 선택한 다음, 선택한 행/열의 모든 동전(N개)를 뒤집을 수 있습니다. N의 범위가 크지 않지만, 나올 수 있는 경우의 수는 어마어마하기 때문에 단순히 무식한 브루트포스 알고리즘으로는 풀기 힘듭니다. 이 때, 우리는 문제를 단순화시킬 수 있습니다.

 

문제 해결하기

만약 가장 무식한 브루트포스 알고리즘으로 해결한다면 얼마의 시간복잡도를 가지고 있을까요? 우선, 우리가 선택할 수 있는 선택지는 총 2N개 입니다. 그리고 각각의 선택지에서 필요한 처리는 2차원 배열에서의 처리이기 때문에 N*N번의 처리가 필요합니다. 따라서, 이 모든 처리를 합쳐보면 O(22N*N2) 의 시간복잡도를 가지게 됩니다. N은 최대 20이기 때문에 단순히 대입해보면 대략 400조에 해당하는 값이 나옵니다. 400조의 경우의 수를 모두 살펴보려면 1초는 턱없이 부족하다는 사실은 누구나 알 수 있습니다. 따라서, 문제를 좀 더 단순화시켜야 합니다.

 

문제를 풀기 위한 아이디어는 바로 N*N개의 동전을 뒤집을 때에는 순서가 중요하지 않다는 사실입니다. 어떤 순서로 뒤집든지 각각의 동전에는 영향을 끼치지 않습니다. 그렇다면 단순하게 모든 행을 뒤집은 다음에 열을 뒤집으면 어떨까요? 이렇게 단순하게 처리하면 우리가 얻을 수 있는 시간적 여유는 어마어마합니다. 우선, 모든 행을 뒤집는 데에는 2N번의 연산이 필요합니다. 이렇게 뒤집은 다음에 어떤 열을 뒤집을지 고민해봐야 하는데, 사실 고민할 필요도 없습니다. 각각의 행은 서로에게 영향을 미치지 않습니다. 따라서, 행의 모든 동전을 살펴본 다음, 뒷면(T)이 많으면 뒤집어주면 됩니다. 그러면 전체 N*N개의 동전 시점에서 보았을 때, 뒷면(T)이 감소하게 됩니다. 그럼 우리는 모든 경우의 수를 살펴보는 대신, (2N * N)개의 경우만을 확인하면 문제를 해결할 수 있습니다.

 

소스코드

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
#include <stdio.h>
#include <algorithm>
#define NMAX 20
using namespace std;
int N, cntMin, cnt;
char t[NMAX];
int inp[NMAX][NMAX], tmp[NMAX][NMAX];
void sv(int row) {
    // 초깃값 설정
    for(int i=0;i<N;i++) {
        for(int j=0;j<N;j++) {
            if(row & (1<<i)) tmp[i][j] = 1-tmp[i][j];
            else tmp[i][j] = inp[i][j];
        }
    }
    // 열 뒤집기
    int tcnt;
    for(int j=0;j<N;j++) {
        tcnt = 0;
        for(int i=0;i<N;i++) tcnt += tmp[i][j];
        if(tcnt > N/2) cnt += (N-tcnt);
        else cnt += tcnt;
    }
}
int main() {
    // 입력
    scanf("%d", &N);
    for(int i=0;i<N;i++) {
        scanf("%s", t);
        for(int j=0;j<N;j++) {
            tmp[i][j] = inp[i][j] = ( t[j]=='H' ? 0:1 );
        }
    }
    // 브루트포스
    cntMin = NMAX*NMAX;
    for(int i=0;i<(1<<N);i++) {
        cnt = 0;
        sv(i);
        // 최솟값 확인
        cntMin = min( cntMin, cnt );
    }
    // 출력
    printf("%d", cntMin);
}
 cs

후기

시간복잡도를 어떻게 줄일 수 있을지 고민을 많이 했던 문제입니다. 추상화 과정을 통해 문제를 나누는 방식을 배울 수 있는 좋은 문제라고 생각합니다. 별다른 기법이 필요없고, 추상화 과정이 중요한 문제라 알고리즘을 공부하는 사람에게 추천하고 싶은 문제입니다.

저작자표시 비영리 동일조건 (새창열림)