백준 15650 N과 M (2)

문제 링크: https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

조합 (combination)을 출력하는 문제이다.

예를 들어 n = 4, m = 2인 경우에

1 2, 1 3, 1 4, 2 3, 2 4, 3 4와 같이 총 4C2 = 6가지 경우를 출력해야 한다.

 

순열에서와 같이 이미 사용했는지 여부를 표시할수 있는 used 배열이 필요가 없다. 

start라는 변수가 하나 추가되어있는데, start보다 큰 숫자가 더 뒤의 index에서 나올수가 절대로 없기 때문이다.

따라서 a배열의 idx칸에 들어갈 숫자를 결정할때는 순열처럼 1부터 n까지 훑는것이 아니라, start부터 훑으면 된다.

#include <bits/stdc++.h>
using namespace std;
 
int n, m, a[10];
 
void solve(int start, int idx) {
    if(idx == m) {
        for(int i = 0; i < m; i++)
            cout << a[i] << ' ';
        cout << '\n';
        return;
    }
 
    for(int i = start; i <= n; i++) {
        a[idx] = i;
        solve(i + 1, idx + 1);
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> m;
    solve(1, 0);
    return 0;
}
 

위코드는 모든 경우의수를 탐색하기 때문에 시간복잡도가 O(n!)이지만, 아래코드는 각 숫자들을 포함할지 안할지 결정하면서 진행하므로 시간복잡도가 O(2^n)인 코드로서, 더 빠르다.

#include <bits/stdc++.h>
using namespace std;
 
int n, m, a[10];
 
void solve(int start, int idx) {
    if(idx == m) {
        for(int i = 0; i < m; i++)
            cout << a[i] << ' ';
        cout << '\n';
        return;
    }
    if(start > n) return;
 
    a[idx] = start;
    solve(start + 1, idx + 1);
    solve(start + 1, idx);
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> m;
    solve(1, 0);
    return 0;
}