인프런 커뮤니티 질문&답변
작성한 질문수
4-B 질문있습니다 :)
작성
·
153
·
수정됨
0
안녕하세요 선생님 🙂
이번 문제 진짜 어려운 문제인거 같더라구요;; ㅎㅎ
문제를 풀면서 몇가지 풀리지 않는 의문이 있어서 질문 드립니다.
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개보다 작게 만들 수 없다라는 조건이 있는데요, 이 처리를 안해도 되는 이유가 궁금합니다.
답변 1
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;
}감사합니다.
안녕하세요 유태님 ㅎㅎ 답변 수정했습니다. 다시 봐주세요.