백준 1285번 동전 뒤집기

문제 링크입니다: https://www.acmicpc.net/problem/1285

1285번: 동전 뒤집기

 

얼핏 보면 시간 복잡도가 O(2^40)으로 보여 시간 안에 풀지 못할 문제처럼 보이는 문제였습니다.

하지만 다음과 같이 문제를 쪼개면 시간 내 풀 수 있는 문제입니다. (시간 복잡도: 400 * 2^20)

• 가능한 모든 조합에 대해 열을 직접 뒤집어 본다 (시간 복잡도: O(2^20))
• 열은 이미 뒤집혔고 행을 뒤집을 차례인데 행 내 뒷면 동전 개수를 파악하면 직접 뒤집을 필요가 없습니다. (시간 복잡도: O(20 * 20))
  • 앞면이 더 많으면 뒤집을 필요가 없고
  • 뒷면이 더 많으면 뒤집는다
  • 위 내용을 토대로 직접 뒤집지 않고 `sum += min(temp, N - temp)`로 대체 가능

 

	#include <iostream>
	#include <string>
	#include <vector>
	#include <algorithm>
	using namespace std;
	const int MAX = 20 + 2;
	const int INF = 987654321;
	int result = INF;
	int N;
	int coins[MAX];
	void func(int idx)
	{
	if (idx == N)
	{
	int sum = 0;
	// 행을 뒤집을지 여부 파악
	for (int i = 1; i < (1 << N); i *= 2)
	{
	int temp = 0;
	for (int j = 0; j < N; j++)
	{
	if (i & coins[j])
	{
	temp++;
	}
	}
	sum += min(temp, N - temp);
	}
	result = min(result, sum);
	return;
	}
	// 열을 뒤집는 경우와 뒤집지 않는 경우 모두 살펴봐야 함
	func(idx + 1);
	coins[idx] = ~coins[idx]; // 비트마스킹 기법을 이용하면 간단히 뒤집을 수 있음
	func(idx + 1);
	}
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	// 주어진 문자열을 T를 기준으로 생성한 비트로 대체
	for (int i = 0; i < N; i++)
	{
	string s;
	cin >> s;
	int bit = 1;
	for (int j = 0; j < N; j++)
	{
	if (s[j] == 'T')
	{
	coins[i] |= bit;
	}
	bit *= 2;
	}
	}
	func(0);
	cout << result << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2022

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

 

참고

인프런 10주완성-코딩테스트 - 큰돌 강사님