[BOJ]1285번: 동전 뒤집기 (c++)

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

1285번: 동전 뒤집기

 

그리디 + 브루트 포스 + 백트랙킹

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;

int flip(vector<unsigned int>& coins, int row)
{
	if (row == N)
	{
		// 각 열의 T개수를 더해 전체 T개수 구하고 반환
		int total = 0;
		for (int i = 0; i < N; ++i)
		{
			int col_t_cnt = 0;
			for (int j = 0; j < N; ++j)
			{
				if (coins[j] & (1 << i))
				{
					++col_t_cnt;
				}
			}
			// 각 열을 뒤집은 경우, 뒤집지 않은 경우 중에서 더 작은 T값 더하기
			total += min(col_t_cnt, N - col_t_cnt);
		}

		return total;
	}

	// row행을 뒤집지 않은 경우
	int unfliped_t_cnt = flip(coins, row + 1);

	// row행을 뒤집은 경우
	coins[row] = ~coins[row];
	int fliped_t_cnt = flip(coins, row + 1);

	// 둘 중 더 작은 T 개수 반환
	return min(unfliped_t_cnt, fliped_t_cnt);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	// 입력 -> 비트마스크 벡터로 만들기
	cin >> N;
	vector<unsigned int> coins(N);
	for (int i = 0; i < N; ++i)
	{
		string line;
		cin >> line;
		for (int j = 0; j < N; ++j)
		{
			if (line[j] == 'T')
			{
				coins[i] |= (1 << j);
			}
		}
	}

	// 동전 뒤집기 최소 T 개수 출력
	cout << flip(coins, 0);

	return 0;
}

 

 

TIP1

동전은 앞/뒤 밖에 없으므로,

비트마스크를 활용하면 더 간단히 뒤집을 수 있다.

 

 

TIP2

행을 어떻게 뒤집느냐에 따라서 열의 뒤집기 여부가 결정된다.

그런데 행을 뒤집는 기준을 쉽게 정의내리기가 어렵다.

한 행에서는 T/H 개수가 같다 하더라도 뒤집는다면 T의 위치를 옮겨주는 효과가 있기 때문이다.

(-> 그러면 새로운 T위치에서의 열이 뒤집는게 낫겠다는 판단을 할수도 있다)

 

첫째 줄에 20이하의 자연수 N이 주어진다

그리고 마침 숫자도 아주 작으므로... 다 해보자!

각 행을 뒤집는 경우, 안뒤집는 경우를 모두 계산하여 (백트랙킹)

행의 뒤집기를 다 마친 다음에, 열을 뒤집기 시작한다.