인프런 커뮤니티 질문&답변

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

안녕하세요 큰돌님 강의 잘듣고 있습니다.

해당문제 관련해서 질문이 있는데요.

일단 비트마스킹을 이용한 풀이법은 숙지했습니다.

근데 비트마스킹을 안쓰고 풀었을때 처음에 틀렸었는데 제가 아래 올린코드에서 Reverse함수의 기저사례 단락에서 "--->이부분!" 이라고 주석표시한 부분 관련해서 궁금한게 있습니다.

문제에서 동전의 뒤집기 갯수가 2보다 작을수는 없다고 해서, 전 처음에 이게 문제가 답에대한 제한조건을 걸었다고 생각해서 저렇게 2보다 큰 경우에만 min값을 갱신하도록 코드를 짰었는데요.

저 부분을 없애야 정답이더라구요.

큰돌님 풀이에서도 2에 대한 제한조건을 거는 부분은 없는것 같은데, 문제에서 해당 예제에관한 설명이 답의 범위에 대해서 제한을 걸어놓은게 아니라 그냥 " 뒷면갯수가 2보다 작은게 불가능하다" 라고 설명해주는 부분인데 제가 잘못이해한건가요??

#include <iostream>
#include <vector>
#include <string>
#include <thread>
#include <mutex>
#include <limits.h>

using namespace std;

int n;
int coin[21][21];
int minVal=INT_MAX;

void Change(int i, int j) //요소 하나 바꾸기
{
	if (coin[i][j] == 1)
		coin[i][j]= 0;
	else
		coin[i][j]= 1;
}
void ChangeAll(int length, char hw ,int fix) // 한줄 바꾸기('h' : 행 고정 / 'w' : 열 고정)
{
	if (hw == 'h') 
		for (int i = 0; i < length; ++i)
			Change(fix, i);

	if (hw == 'w') 
		for (int i = 0; i < length; ++i)
			Change(i, fix);

}

void Reverse(int length, char fix, int fixPos) // 행 다 모든 경우의수로 다 뒤집고 열 하나씩 뒤집어보기
{

	if (fixPos == length) {
		int ret = 0;
		for (int i = 0; i < length; ++i) {
			int sum = 0;
			for (int j = 0; j < length; ++j){
				sum += coin[j][i];
			}
			if ((length - sum) > sum) 
				ret += sum;
			else
				ret += (length - sum);
		}
		if(ret>=2)  //------------------> 이부분!
			minVal = min(minVal, ret);
		return;
	}

	if (fix == 'h'){
		for (int i = 0; i < 2; ++i){
			ChangeAll(length, fix, fixPos);
			Reverse(length, fix, fixPos + 1);
		}
	}
	if (fix == 'w') {
		for (int i = 0; i < 2; ++i){
			ChangeAll(length, fix, fixPos);
			Reverse(length, fix, fixPos + 1);
		}
	}
}

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

	cin >> n;
	for (int i = 0; i < n; ++i) {
		string s;
		cin >> s;
		for (int j = 0; j < n; ++j) {
			if (s[j] == 'H')
				coin[i][j] = 'H' - 'H' + 1;
			else
				coin[i][j] = 'T' - 'T';
		}

	}

	Reverse(n, 'h', 0);
	cout << minVal << '\n';

}