BOJ 15666 · N과 M (12)

알고리즘 분류 : 브루트 포스  

입력받은 N개의 숫자 중에서 M개를 뽑아서 출력하는 문제다. N과 M (8) 문제와 비슷하나, N개의 숫자 중 중복된 숫자가 주어질 수 있다. N과 M (11) 문제에서 for문의 시작 지점만 바꾸면 된다.

---

C++ 소스코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
vector<int> a, v;

void solve(int cnt, int idx) {
    if (cnt == m) {
        for (auto k : v) printf("%d ", k);
        printf("\n");
        return;
    }
    for (int i=idx; i<n; i++) {
        v.push_back(a[i]);
        solve(cnt+1, i);
        v.pop_back();
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<n; i++) {
        int t;
        scanf("%d", &t);
        if (find(a.begin(), a.end(), t) == a.end()) a.push_back(t);
    }
    sort(a.begin(), a.end());
    n = a.size();
    solve(0, 0);
    return 0;
}

---

Python 3 소스코드

from sys import stdin, stdout
input = stdin.readline
print = stdout.write

n, m = map(int, input().split())
a = sorted(set(list(map(int, input().split()))))
v = []

def solve(cnt, idx):
    if cnt == m:
        print(' '.join(map(str, v))+'\n')
        return
    for i in range(idx, len(a)):
        v.append(a[i])
        solve(cnt+1, i)
        v.pop()

solve(0, 0)

---

참고

• 백준 온라인 저지 : BOJ 15666
• N과 M (8)
• N과 M (11)