BOJ 15651 · N과 M (3)

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

N개의 숫자 중에서 M개를 뽑는 문제다. 숫자를 뽑을 때 같은 수를 여러번 골라도 된다. 이 문제는 N과 M (1) 문제의 소스코드에서 check 배열만 사용하지 않으면 된다.

---

C++ 소스코드

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

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

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

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

---

Python 3 소스코드

from sys import stdin
input = stdin.readline

n, m = map(int, input().split())
a = []

def solve(cnt):
    if cnt == m:
        print(" ".join(map(str, a)))
        return
    for i in range(n):
        a.append(i+1)
        solve(cnt+1)
        a.pop()

solve(0)

---

참고

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