BOJ 15649 · N과 M (1)

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

N개의 숫자 중에서, M개만 뽑아서 출력하는 문제다. 재귀 함수를 이용하여 구현할 수 있다.

• 사용 여부를 확인할 배열 check를 N 사이즈로 만들어둔다.
• 1부터 N까지 재귀 함수를 호출한다. 
• 숫자 X를 사용했으면, check[X]를 true로 한다.
• check가 true라면 재귀 함수를 호출하지 않고 넘어간다.
• 사용한 숫자를 리스트에 담아두고, 리스트의 길이가 M이 되면 리스트를 출력한다.

---

C++ 소스코드

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

int n, m;
bool check[8];
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++) {
        if (!check[i]) {
            check[i] = true;
            a.push_back(i);
            solve(cnt+1);
            a.pop_back();
            check[i] = false;
        }
    }
}

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())
check = [False]*n
a = []

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

solve(0)

✓ 순열 (Permutation)로 구현할 수도 있다.

✓ 파이썬은 itertools에 있는 permutations를 이용하면 편하다.

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

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

---

참고

• 백준 온라인 저지 : BOJ 15649