1285번: 동전 뒤집기

동전 뒤집기

 

시간 제한             메모리 제한          제출             정답             맞힌 사람             정답 비율

6 초

128 MB

4372

1820

1263

46.145%

문제

 

N2개의 동전이 N행 N열을 이루어 탁자 위에 놓여 있다. 그 중 일부는 앞면(H)이 위를 향하도록 놓여 있고, 나머지는 뒷면(T)이 위를 향하도록 놓여 있다. <그림 1>은 N이 3일 때의 예이다.

<그림 1>

이들 N2개의 동전에 대하여 임의의 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업을 수행할 수 있다. 예를 들어 <그림 1>의 상태에서 첫 번째 열에 놓인 동전을 모두 뒤집으면 <그림 2>와 같이 되고, <그림 2>의 상태에서 첫 번째 행에 놓인 동전을 모두 뒤집으면 <그림 3>과 같이 된다.

<그림 3>의 상태에서 뒷면이 위를 향하여 놓인 동전의 개수는 두 개이다. <그림 1>의 상태에서 이와 같이 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업을 계속 수행할 때 뒷면이 위를 향하도록 놓인 동전의 개수를 2개보다 작게 만들 수는 없다.

N2개의 동전들의 초기 상태가 주어질 때, 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업들을 수행하여 뒷면이 위를 향하는 동전 개수를 최소로 하려 한다. 이때의 최소 개수를 구하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위를 향하도록 놓인 경우 H, 뒷면이 위를 향하도록 놓인 경우 T로 표시되며 이들 사이에 공백은 없다.

 

출력

첫째 줄에 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업들을 수행하여 뒷면이 위를 향하여 놓일 수 있는 동전의 최소 개수를 출력한다.

 

예제 입력 1 복사

3
HHT
THH
THT

예제 출력 1 복사

2

 

 

흐름

 

 

선생님 코드

#include <bits/stdc++.h>
using namespace std;

const int INF = 987654321;
int n, a[44],ret=INF;
string s;

void go(int here){
    if(here==n+1){ //n행 위치까지 오면(하나의 케이스 완성)
        int sum = 0;
        //열에서 T의 개수 구하기
        for(int i=1;i<=(1<<(n-1)); i*=2){ //열마다 이진수값
            int cnt=0;
            for(int j=1;j<=n;j++) if(a[j]&i) cnt++; //각 행마다 열의 자리수값(1로 표시되면)이 있으면 cnt++
            sum += min(cnt, n-cnt); //T의 개수가 뒤집은 것과 비교하여 더 작은 것을 더하기
        }
        ret = min(ret,sum); //케이스마다 T의 개수 최소값 비교하여 저장하기
        return;
    }
    a[here]=~a[here]; //반전시키기
    go(here+1);
    a[here]=~a[here]; //복원하기
    go(here+1);

}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> s; //행 입력받기
        int value=1;
        for(int j=0;j<s.size();j++){ //각 행마다 값으로 저장받기 
            if(s[j]=='T') a[i]|=value;
            value *=2;
        }
    }
    //2. 행 뒤집는 모든 경우의 수 구하기
    go(1); //1행부터 시작
    //3. 정답 출력하기
    cout << ret << "\n";
    return 0;
}

 

• 두 가지 경우의 수만 존재할때 (H가 0이고, T가 1일때) T의 최소 개수를 구하고 싶다면 뒤집을 때와 뒤집지 않을 때를 비교해야한다. 이때 min(cnt, n-cnt)로 하면 뒤집을때와 뒤집지 않을때의 T의 개수를 비교하여 최소개수를 알 수 있다.
•  행마다 값으로 저장받고 자리수가 있는지 확인하면 된다.
• n의 최대가 20이므로 비트마스킹을 할 수 있다.(최대 30까지 가능)
• 완전탐색시 return 명시하기
• 자리수마다 값 더하는 코드(이진수=>십진수로 표현하기)

 for(char c:s){
            if(c=='H') a[i] |= value; //a[i]는 0부터 시작하므로 바로 더하기
            value*=2;
}

 

다시 정리한 코드

#include <bits/stdc++.h>
using namespace std;

const int INF = 987654321;
int n, a[24], ret=INF, sum;
string s;

void go(int here){
    if(here==n+1){ //하나의 케이스 완성되면
        sum=0;
        for(int i=1;i<=(1<<(n-1));i*=2){ //각 자리수에 대해
            int cnt=0;
            for(int j=1;j<=n;j++){ //각 행에 대해
                if(a[j] & i){
                    cnt++; //T 존재하면 cnt
                }
            }
            sum +=min(cnt,n-cnt); //뒤집을때의 최소개수 고려
        }
        ret = min(sum, ret);
        return; //종료 조건 명시하기
    }
    //완전탐색
    a[here]= ~a[here];
    go(here+1);
    a[here]=~a[here]; //복원
    go(here+1);
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> n; 
    for(int i=1;i<=n;i++){
        cin >> s;
        int value=1;
        for(char c:s){
            if(c=='H') a[i] |= value; //a[i]는 0부터 시작하므로 바로 더하기
            value*=2;
        }
    }
    //2. 완전탐색 수행
    go(1);
    //3. 정답 출력
    cout << ret << "\n";

}