작성한 질문수 79

0

안녕하세요 유태님 ㅎㅎ

이부분은 go()함수가 1부터 시작하고 n까지 가는 함수입니다.

n = 3일 때

go(1), go(2), go(3)까지는 가야하는 것이죠.

이 때 n + 1인 4일 때 종료해야 a[here] = ~a[here]부분이 잘 동작할 수 있습니다.

a[3]일 때도 한번 뒤집는 경우의 수를 판단해야하기 때문에 n + 1까지 가야 n까지의 경우의 수를 판단할 수 있습니다.

ex) n이 3일 때는 총 8개의 경우의 수를 판단해야 하는데요.

aaa

aab

aba

abb

baa

bab

bba

bbb

디버깅 코드 찍어보시면 총 8번이 나오는 것을 볼 수 있습니다.

#include<bits/stdc++.h>
#define maxn 200005
typedef long long ll;
using namespace std;   
const int INF = 987654321;
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1}; 
int n, a[44], ret = INF;
string s; 
void go(int here){ 
	if(here == n + 1){
        cout << here << "\n";
		int sum = 0; 
		for(int i = 1; i <= (1 << (n - 1)); i *= 2){
			int cnt = 0; 
			for(int j = 1; j <= n; j++) if(a[j] & i)cnt++;
			sum += min(cnt, n - cnt); 
		}
		ret = min(ret, sum);
		return;
	} 
	go(here + 1);
	a[here] = ~a[here];
	go(here + 1);
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> n; 
	for(int i = 1; i <= n; i++){
		cin >> s; 
		int value = 1; 
		for(int j = 0; j < s.size(); j++){
			if(s[j] == 'T')a[i] |= value; 
			value *= 2;
		}
	}   
	go(1);
	cout << ret << "\n";
    return 0;
}

감사합니다.