: 처음에는 선택한 원소의 개수도 재귀로 넘겼는데 S가 0이 아닌 경우는 공집합을 포함해도 경우의 수에 포함 되지 않으므로
마지막에 계산할 때, S가 0인 경우 1가지 경우의 수를 빼주면 됨.
- Bit Mask로 구현했을 때
: 좀 더 구현에 연습이 필요함
재귀 소스코드
#include<iostream>
using namespace std;
int n, s, cnt = 0;
int v[21];
void dfs(int pos, int sum){
if (pos == n){
if(sum == s)
cnt++;
return;
}
dfs(pos + 1, sum + v[pos]);
dfs(pos + 1, sum);
return;
}
int main(void){
cin >> n >> s;
for (int i = 0; i < n; i++)
cin >> v[i];
dfs(0, 0);
if(s == 0) cnt--;
cout << cnt << "\n";
return 0;
}
Bit Mask 소스코드
#include<iostream>
using namespace std;
int n, s, ans;
int v[21];
int main(void){
freopen("Text.txt", "r", stdin);
cin >> n >> s;
for (int i = 0; i < n; i++)
cin >> v[i];
// 공집합을 제외한 모든 부분집합(000...001 ~ 111...111)
for (int i = 1; i < (1 << n); i++){
int sum = 0;
// 하나의 부분집합에서 각 원소가 부분집합에 속하는지 확인
for (int j = 0; j < n; j++)
if ((1 << j) & i)
sum += v[j];
if (sum == s)
ans++;
}
cout << ans << "\n";
return 0;
}
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]
- 조합을 재귀 말고 쉽게 구현할 수 있는 방법이 있을까? 아직 지하 밑바닥에 있어서 좀 더 경험이 필요할 듯
- 9C2를 for로 구현했을 때 sort에서 a+10을 해버렸....왜 0이 나오나 했네
소스코드 : 9C2
#include<iostream>
#include<algorithm>
using namespace std;
int a[9];
int main(void){
int sum = 0;
for (int i = 0; i < 9; i++){
cin >> a[i];
sum += a[i];
}
for (int i = 0; i < 8; i++){
for (int j = i + 1; j < 9; j++){
if (a[i] + a[j] == sum - 100){
a[i] = 1000;
a[j] = 1000;
}
}
}
sort(a, a + 9);
for (int i = 0; i < 7; i++)
cout << a[i] << "\n";
return 0;
}
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]
- 두 자릿수 입력만 받는다면 O(1)이겠지만, 3자릿수가 넘어가면 각각의 수에 대해 확인해야하므로 O(N)
1) 각 자릿수의 차를 직접 구해보기
- 세 번째 자릿수 - 두 번째 자릿수 == 두 번째 자릿수 - 첫 번째 자릿수
소스코드
#include<iostream>
using namespace std;
int n, cnt = 0;
int main(void){
cin >> n;
for (int i = 1; i <= n; i++){
if (i < 100)
cnt++;
else {
int f = i % 10;
int s = (i / 10) % 10;
int t = i / 100;
if ((f - s) == (s - t))
cnt++;
}
}
cout << cnt << "\n";
return 0;
}
2) 등차수열의 특징을 활용
- 사실 특징이라고 할게 있나...
- a, a+d, a+2d ... 이므로 a + a+2d = (a+d) * 2
소스코드
else {
int f = i % 10;
int s = (i / 10) % 10;
int t = i / 100;
if (f+t == 2*s)
cnt++;
}
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]
: 시간복잡도 : 첫 짝이 없는 친구를 고르는 경우(1)(0 학생이 무조건 처음이므로) * 0학생과 친구인 관계(N-1) * 0과 0 친구를 제외한 다음 짝이 없는 친구를 고르는 경우(N-2) * 두 번째 고른 학생과 친구인 관계(N-3) * ... * 1 = 9! ≒ 360,000
즉, 1억번 내에 들어옴
: 공간복잡도 : global variable - int * 3 = 12byte
local variable - bool * 100 + bool * 10 = 110byte
≒ 122byte
즉, 2^16kb 이내
5, 6) 계획 수행하기 및 회고하기
실패한 소스코드
- 중복처리를 안해줌
- 해당 코드에서는 (0, 1) (2, 3) 과 (2, 3) (0, 1) 이 다른 경우로 판단함.
#define LOCAL_TEST
#include<iostream>
using namespace std;
int n, m, cnt;
// isfriend : 두 명이 친구인지 여부
// check : 친구랑 짝이 지어졌는지 여부
// remain : 짝지을 학생이 몇명 남아있는지 여부
void dfs(bool isfriend[][10], bool check[10], int remain){
// 짝지을 학생이 없으면 하나의 경우를 찾았으므로 cnt++
if (remain == 0){
cnt++;
return;
}
// 짝을 지을 첫번째 학생 선택
for (int i = 0; i < n; i++){
if (!check[i]){
// i 번째 학생과 친구인 학생
for (int j = 0; j < n; j++){
// i와 j가 친구이고 j가 다른 친구와 짝짓지 않은 경우, 친구임을 check 배열에 없데이트하고 재귀
if (isfriend[i][j] && !check[j]){
check[i] = check[j] = true;
dfs(isfriend, check, remain - 2);
check[i] = check[j] = false;
}
}
}
}
return;
}
int main(void){
#ifdef LOCAL_TEST
freopen("input.txt", "r", stdin);
#endif
int T;
cin >> T;
while (T--){
n = m = cnt = 0;
cin >> n >> m;
bool isfriend[10][10] = { false };
bool check[10] = { false };
for (int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
isfriend[a][b] = true;
}
dfs(isfriend, check, n);
cout << cnt << "\n";
}
#ifdef LOCAL_TEST
fclose(stdin);
#endif
return 0;
}
성공한 소스코드
- 중복처리는 시작점을 고정하는게 제일 좋음
- 단, 이 방법은 a와 b가 친구이면 isfriend[a][b] = isfriend[b][a] = true로 해줘야 (1,2) (3,0) 같은 경우를 골라낼 수 있음
- 아니면 0과 3이 친구가 아니므로 경우의 수가 빠지게 됨
※ 시간복잡도 : 학생 하나 고르는데 걸리는 시간(1) * 고른 학생과 친구인 학생 고르는데 걸리는 시간(N-1) * 두명을 제외한 학생 한명과 그 친구를 고르는데 걸리는 시간(N-3) * ... * 1= 9 * 7 * 5 * 3 * 1 = 945
공간복잡도 : 위 공간복잡도 + 각 재귀마다 int student가 추가됨(int * (9 * 7 * 5 * 3 * 1) = 3780byte
즉, 3920byte
#define LOCAL_TEST
#include<iostream>
using namespace std;
int n, m, cnt;
// isfriend : 두 명이 친구인지 여부
// check : 친구랑 짝이 지어졌는지 여부
// remain : 짝지을 학생이 몇명 남아있는지 여부
void dfs(bool isfriend[][10], bool check[10], int remain){
// 짝지을 학생이 없으면 하나의 경우를 찾았으므로 cnt++
if (remain == 0){
cnt++;
return;
}
// 짝을 지을 첫번째 고정학생 선택
int student = 0;
for (int i = 0; i < n; i++){
if (!check[i]){
student = i;
break;
}
}
// student 학생과 친구인 학생
for (int j = 0; j < n; j++){
// student와 j가 친구이고 j가 다른 친구와 짝짓지 않은 경우, 친구임을 check 배열에 없데이트하고 재귀
if (isfriend[student][j] && !check[j]){
check[student] = check[j] = true;
dfs(isfriend, check, remain - 2);
check[student] = check[j] = false;
}
}
return;
}
int main(void){
#ifdef LOCAL_TEST
freopen("input.txt", "r", stdin);
#endif
int T;
cin >> T;
while (T--){
n = m = cnt = 0;
cin >> n >> m;
bool isfriend[10][10] = { false };
bool check[10] = { false };
for (int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
isfriend[a][b] = isfriend[b][a] = true;
}
dfs(isfriend, check, n);
cout << cnt << "\n";
}
#ifdef LOCAL_TEST
fclose(stdin);
#endif
return 0;
}
※ 왜 종만북의 코드와 속도는 동일하지만 종만북 코드로 제출한 사람들의 코드는 0ms도 있음
