BOJ 15650 · N과 M (2)

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

N개의 숫자 중에서 M개를 뽑아서 출력하는 문제다. 단, 중복된 수열이 없어야 하고, 오름차 순으로 출력해야 한다. N과 M (1)의 코드에서 for문의 시작 지점을 수정하면 된다. 시작 지점은 이전에 뽑은 숫자+1 이다. 숫자+1을 다음 재귀 함수 호출에 전달하면 된다.

---

C++ 소스코드

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

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

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

int main() {
    scanf("%d %d", &n, &m);
    solve(0, 0);
    return 0;
}

---

Python 3 소스코드

from sys import stdin
from itertools import combinations
input = stdin.readline

n, m = map(int, input().split())
for k in combinations([i for i in range(1, n+1)], m):
    print(" ".join(map(str, k)))

✓ C++에서 구현한 방법과 마찬가지로 구현할 수 있지만, 조합(Combination) 방법으로 풀 수 있다.

✓ 파이썬은 itertools의 combinations를 이용하면 간단하다.

---

참고

• 백준 온라인 저지 : BOJ 15650
• N과 M (1)