[백준] 1285 동전 뒤집기 - Greedy / Java

• 문제 링크

1285번: 동전 뒤집기

 

• 풀이 과정

문제에 제시된 조건에 의하면 각 동전의 값은 대응되는 행 또는 열을 변환할 때 그 값이 결정된다.

해당 풀이에서는 n = 3, n * n 의 행렬에서의 행의 변환의 모든 경우의 수를 구하며

이를 1 ~ (1 << n) 범위의 2진수에서 특정 행이 변환되었음을 1로 나타내면 아래와 같다.

모든 행을 변환	111
2개의 행을 선택하여 변환	011, 101, 110
1개의 행을 선택하여 변환	001, 010, 100

이렇게 행을 뒤집는 각각의 경우의 수에서 열을 기준으로 반복문을 수행하여

현재 위치의 AND 연산의 결과가 1 일 경우, 즉 해당 위치가 뒤집힌 행에 속할 경우 XOR 연산을 통해 뒤집고

해당 열의 동전 뒷면의 개수를 나타내는 tail 변수에 tail++ 을 수행한다.

 

이때 해당 열을 뒤집거나 뒤집지 않는 경우에서의 동전 뒷면의 개수를 

Math.min(tail, n - tail) 을 통해 비교하여 최솟값을 sum 변수에 누적한다.

 

이렇게 sum 은 행을 뒤집는 하나의 경우의 수에서의 동전 뒷면의 최솟값이며

각각의 경우의 수에서의 최솟값을 res 변수에 갱신시켜 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
		int[][] map = new int[n][n];

		for (int i = 0; i < n; i++) {
			String input = br.readLine();
			for (int j = 0; j < n; j++) {
				if (input.charAt(j) == 'T')
					map[i][j] = 1;
			}
		}

		int res = n * n;
		for (int bit = 1; bit <= (1 << n); bit++) {
			int sum = 0;

			for (int x = 0; x < n; x++) {
				int tail = 0;

				for (int y = 0; y < n; y++) {
					int coin = map[y][x];

					if ((bit & (1 << y)) != 0)
						coin = map[y][x] ^ 1;
					if (coin == 1)
						tail++;
				}

				sum += Math.min(tail, n - tail);
			}

			if (sum < res)
				res = sum;
		}

		bw.write(res + "\n");
		bw.flush();
	}

}