4-B 질문있습니다 :)

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

4-B

작성

수정됨

안녕하세요 선생님 🙂

이번 문제 진짜 어려운 문제인거 같더라구요;; ㅎㅎ

문제를 풀면서 몇가지 풀리지 않는 의문이 있어서 질문 드립니다.

http://boj.kr/2f42a7b2bc644e2e8db2ab8729507b5d

선생님께서는 go함수의 here = n + 1인 경우에 함수를 리턴시키셨는데요, n = 3일 경우에 go(1)부터 시작하여 go(4)까지 재귀를 돌리면 총 8번의 go(4)를 사용합니다.

하지만, go함수의 리턴시키는 조건이 here = n일 경우에는 go(3)까지 총 4번의 go(3)을 사용합니다.

입력 조건의 n이 3일 경우에 3번만 돌리면 된다고 생각하는데요, 경우의 수를 추가로 넣어주신 이유가 궁금합니다.

추가로, 뒷면이 위를 향하도록 놓인 동전의 개수를 2개보다 작게 만들 수 없다라는 조건이 있는데요, 이 처리를 안해도 되는 이유가 궁금합니다.

c++코딩-테스트

답변 1

큰돌

지식공유자

안녕하세요 유태님 ㅎㅎ

이부분은 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;
}

감사합니다.

큰돌

지식공유자

안녕하세요 유태님 ㅎㅎ 답변 수정했습니다. 다시 봐주세요.

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

4-B 질문있습니다 :)