[C++] 백준(BOJ) - 1285 : 동전 뒤집기

13 Nov 2023 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 알고리즘
• 풀이
• 코드
• 평가

문제

백준(BOJ) - 1285 : 동전 뒤집기(링크)

알고리즘

1. 브루트포스
2. 백트래킹
3. 비트마스킹

풀이

1. 시간복잡도 어림잡아 계산해보기
   • O($2^{40}$) 일반적인 백트랙킹으로는 풀기 힘들다\
   • 행만 뒤집으면 열의 최적값은 정해져있다
   • 실제 시간복잡도 : $2^{20}$
2. String을 숫자로 생각하기

   • HHT 4 001 (100)
     THH 1 100 (001)
     THT 5 101 (101)

   • String 자료형을 배열형태로 비트마스킹을 통해 저장
3. 행 기준으로 배열 뒤집기를 한 것과 안한 것을 재귀함수로 만들기
4. 기저조건에서 열을 기준으로 전체 탐색
   • 1번 인덱스부터 (1 부터) 1 « (n - 1) 까지 열을 기준으로 체크
   • 행바다 해당 인덱스에 T가 존재 하는지 아닌지 체크
   • T를 최소화 하는 개수 찾기
   • 위의 과정을 가장 최소화 시키는 수를 저장

코드

// BOJ-1285 : 동전 뒤집기
#include<bits/stdc++.h>
using namespace std;

const int INF = 2147000000;
int n, a[44], res = INF;

void go(int here)
{
	if (here == n + 1)
	{
		int sum = 0;
		for (int i = 1; i <= (1 << (n - 1)); i*= 2) // 열을 기준으로
		{
			int cnt = 0;
			for (int j = 1; j <= n; j++) if (i & a[j]) cnt++; // 행마다 해당 인덱스를 체크
			sum += min(cnt, n - cnt); // 최소값이 되는 T 값 찾기
		}
		res = min(res, sum);
		return;
	}
	go(here + 1);
	a[here] = ~a[here];
	go(here + 1);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		string str;
		cin >> str;

		int value = 1;
		for (int j = 0; j < str.size(); j++)
		{
			if (str[j] == 'T') a[i] |= value; // String 값을 비트마스킹을 통해 int 배열로 저장
			value *= 2;
		}
	}

	//for (int i = 1; i <= n; i++) cout << a[i] << ' '; // 디버깅
	go(1);
	cout << res << '\n';

	return 0;
}

평가

• 구현자체가 조금 어렵고 복잡해 보이는 비트마스킹 문제이다
• 후에 다시 문제를 풀어보는 시간을 갖기로 한다