[백준] 1285번 : 동전 뒤집기 - JAVA [자바]

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

---

그리디와 비트마스킹 알고리즘을 사용하였다.

각 행을 뒤집는 경우의 수는 2^N 개이다.
각 행을 뒤집는 경우의 수마다 열을 뒤집는 경우의 수는 2^N * 2^N 으로 모두 구해서 최소값을 구하려면 시간 초과가 발생한다.

이를 해결하기 위해

1. 행을 뒤집는 경우의 수를 다 구한다. (2^N)
2. 각 행을 뒤집는 경우의 수마다 각 열을 확인해 T 가 더 많으면 뒤집는다.(2^N * N)

그러면 먼저 행을 뒤집는 경우의 수를 구하기 위해 비트마스킹을 사용할 수 있다.

행을 뒤집는 경우를 1, 뒤집지 않은 경우를 0으로 하고 N은 3인 경우를 예를 들어보자.

0 일 경우 이진수는 000이 되며 이는 아무 행도 뒤집지 않은 공집합이라고 생각한다.
1 일 경우 이진수는 001이 되며 이는 1 번째 행만 뒤집은 경우라고 생각한다.
6 일 경우 이진수는 110이 되며 이는 3 번째, 2 번째 행만 뒤집은 경우라고 생각한다.

즉, 0 부터 (1<<N) 까지 돌면서 탐색한다면 행을 뒤집는 모든 경우의 수를 구할 수 있다.

또한 if ((bit & (1 << i)) != 0) 식을 활용하여 만약 bit가 1 즉, 이진수로 001일 경우 1 번째 행만 뒤집은 경우이기 때문에 (1 << i) -> (1 << 0) 는 001 이 되고 위의 식의 값은 1이 되기 때문에 이때의 i(0) 에 해당하는 행을 뒤집으면 된다.

// 아무 행도 뒤집지 않은 공집합(0)부터
// 모든 행을 뒤집은 (1<<N)-1까지
// 모든 행을 뒤집는 선택(bit)을 탐색한다
for (int bit = 0; bit < (1 << N); bit++) {
	// 이번 선택에 대해 열을 순회하며 T가 더 많은 열을 뒤집는다
    int sumT = 0;
    // 이번 열 확인
    for (int j = 0; j < N; j++) {
    	int colTCount = 0;
        // 이번 열에서 T의 갯수 확인
        for (int i = 0; i < N; i++) {
        	char tmp = coins[i][j];
            // 만약 이번 선택으로 인해 뒤집어야 하는 행이면 뒤집은 값으로 판별
            // 예) bit가 010 이면 i가 1일때 값이 1이 되므로
            // i는 1 즉, 두번째 행을 뒤집는다.
            if ((bit & (1 << i)) != 0) {
            	tmp = (tmp == 'T') ? 'H' : 'T';
			}
	        if (tmp == 'T') colTCount++;
		}
        // T가 더 많으면 뒤집어야 하므로 뒤집는다고 생각하고
        // 혹은 T가 더 적으면 안뒤집어도 되므로
        // 둘 중 적은 갯수를 더해줌
        sumT += Math.min(N - colTCount, colTCount);
	}
    // 이번 행을 뒤집는 경우의 수에서 T의 갯수를 정답과 비교하여 업데이트
    answer = Math.min(answer, sumT);
}

---

public class bj1285 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int answer = N * N;
        char[][] coins = new char[N][N];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            char[] charArray = line.toCharArray();
            for (int j = 0; j < N; j++) {
                coins[i][j] = charArray[j];
            }
        }

        // 아무 행도 뒤집지 않은 공집합(0)부터
        // 모든 행을 뒤집은 (1<<N)-1까지
        // 모든 행을 뒤집는 선택을 탐색한다
        for (int bit = 0; bit < (1 << N); bit++) {
            // 이번 선택에 대해 열을 순회하며 T가 더 많은 열을 뒤집는다
            int sumT = 0;
            // 이번 열 확인
            for (int j = 0; j < N; j++) {
                int colTCount = 0;
                // 이번 열에서 T의 갯수 확인
                for (int i = 0; i < N; i++) {
                    char tmp = coins[i][j];
                    // 예) bit가 010 이면 i가 1일때 값이 1이 되므로
                    // i는 1 즉, 두번째 행을 뒤집는다.
                    // 뒤집어야 하는 행 확인하여 뒤집기
                    if ((bit & (1 << i)) != 0) {
                        tmp = (tmp == 'T') ? 'H' : 'T';
                    }
                    if (tmp == 'T') colTCount++;
                }
                // T가 더 많으면 뒤집어줌
                // 뒤집는다고 생각하고 적은 갯수를 더해줌
                sumT += Math.min(N - colTCount, colTCount);
            }
            answer = Math.min(answer, sumT);
        }

        System.out.println(answer);
        br.close();
    }
}

반례 모음집