[백준/c++] 1285번: 동전 뒤집기

 

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

1285번: 동전 뒤집기

 

이들 N^2개의 동전에 대하여 임의의 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업을 수행할 수 있다.

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

 

[정리]

• 각 행/열 별로 동전을 뒤집을 수 있다.
• 각 동전의 상태에 영향을 미치는 동작: 행 뒤집기, 열 뒤집기
• 뒤집을 때, 안 뒤집을 때 중 T의 개수가 더 적은 쪽으로 뒤집기: min(현재 T 수, N-T 수)

 

이 문제는 혼자서 도저히 풀리지가 않아서 다른 사람들의 코드를 참고해서 공부한 내용을 작성했다.

열 우선으로 배열을 훑으면서 2^n가지의 뒤집기/안 뒤집기 경우의 수를 모두 확인할 수 있다. 이 중에서 가장 작은 뒤집기 횟수를 ans에 넣으면 된다. 비트 마스킹을 이용해서 더 간결하고 빠른 구현을 할 수 있다. 이렇게 경우의 수가 나오고 2가지 경우만 주어지면 비트마스킹을 사용하는 게 좋을 거라는 생각이 들었다.

 

열 우선

 

여기서, 왜 열 우선으로 갔을까 생각이 되어서 i와 j를 반대로 해서 행 우선으로 했는데

행 우선 경우의 수: 1656ms

열 우선 경우의 수: 612ms

시간 차이가 굉장했다. (예전에 자료구조 수업 때 들었던 것이 생각났다)

 

row-major, column-major

row-major: 행 우선순위. row 단위로 저장. 하나의 row를 완전히 저장하고 다음 row 저장

col-major: 열 우선순위. col 단위로 저장. 하나의 col을 저장한 뒤 다음 col을 저장

연속적인 배열 참조 시 cache memory 운용 때문에 row-major로 할지 col-major로 할지 선택하는 것은 중요. 열 우선이 더 빠르다.

 

https://huilife.tistory.com/15

row-major (행 우선), column-major(열 우선)가 왜 중요한가?

 

 

 

---

 

 

전체 코드

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int n, ans = 9999999;
char coin[21][21];

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i=0; i<n; i++) for(int j=0; j<n; j++) cin >> coin[i][j];
    
    for(int k=0; k <(1<<n); k++){
        int sum = 0;
        for(int j=0; j<n; j++){ //행
            int tCnt = 0;
            for(int i=0; i<n; i++){ //열
                char now = coin[i][j];
                if((1<<i) & k) now = (now == 'H') ? 'T' : 'H';
                if(now == 'T') tCnt++; //T: false, H: true
            }
            sum += min(tCnt, n-tCnt);
        }
        ans = min(ans, sum);
    }
    cout << ans << '\n';
    return 0;
}