[그리디 알고리즘] 동전 뒤집기

예제 입력 1

3

HHT

THH

THT

예제 출력 1

2

 

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

1285번: 동전 뒤집기

- 각 행/열 별로 동전을 뒤집을 수 있다. 행렬/전구와 스위치 문제와 유사

- 각 동전의 상태에 영향을 미칠 수 있는 동작은 2가지 이다. (그 행에 속하는 행 뒤집기, 그 열에 속하는 열 뒤집기)

- 그런데, 이미 모든 행에 대해서 뒤집을지 말지 결정되어있다면? 각 열 별로 뒤집을지 말지 결정하여 뒷면(T)의 수가 가장 적게 만들어주면 된다. 

 

- 처음에는 실제로 매 시행마다 배열을 카피해두고 직접 뒤집어보고 그래서 시간 초과가 났다... 카피 배열 만들필요 없이 각 위치별로 탐색할 때 뒤집을지 말지를 정해주면 되고, 뒤집을 때가 뒷면의 수가 더 적은지 아닌지는 MIN(현재 뒷면의 수, N - 현재 뒷면의 수)로 구할 수 있었다.

#include <stdio.h>
#define MIN(a,b) ((a)<(b)?(a):(b))

const int MAX_SIZE = 20;

int N;
char map[MAX_SIZE][MAX_SIZE];

int main(void)
{
	int ans = 2100000000;

	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			while (true)
			{
				scanf("%c", &map[i][j]);

				if (map[i][j] != '\n') break;
			}
		}
	}

	for (int k = 0; k < (1 << N); k++) // 각 행에 대해서 뒤집을지?
	{
		int sum = 0;

		for (int j = 0; j < N; j++) // 열
		{
			int nowT = 0;

			for (int i = 0; i < N; i++) // 행
			{
				char now = map[i][j];

				if ((1 << i) & k)
				{
					if (now == 'T') now = 'H';
					else now = 'T';
				}

				if (now == 'T') nowT++;
			}

			// 이 열을 뒤집는게 이득인지
			sum += MIN(nowT, N - nowT);
		}

		ans = MIN(ans, sum);
	}

	printf("%d\n", ans);

	return 0;
}