[백준 15649] N과 M (1)

🍎[백준 15649] N과 M (1)

문제링크

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

⚾ 코드

# 순열 직접 구현
n, m = map(int, input().split())
cnt = m
numbers = list(range(1, n+1))

res = []


def permutation(pre, now, m):
    if len(now) < m or m == 0:
        return pre

    for i in range(len(now)):
        pre.append(now[i])
        temp = permutation(pre, now[:i]+now[i+1:], m-1)
        if temp and len(temp) == cnt:
            # res.append(temp[:])
            print(*temp)
        pre.pop()


permutation([], numbers, m)
# print(res)

 

🔔 해결 과정 & 깨달은 점

- itertools의 permutations를 쓰지 않고 순열을 직접 구현해보고 싶었다.

 

- 구현한 원리는 다음과 같다.

예를 들어 1,2,3,4 중에서 중복없이 2개를 뽑아 순열을 구한다고 하자.

잘 생각해보면 1, 2, 3, 4에서 2개를 뽑는 것은 1을 뽑고 2, 3, 4중에서 1개를 뽑는 경우의 수와 2를 뽑고 1, 3, 4중에서 1개를 뽑는 경우의 수와 3을 뽑고 1, 2, 4중에서 1개를 뽑는 경우의 수와 4를 뽑고 1, 2, 3 중에서 1개를 뽑는 경우의 수를 합한것과 같다.

식으로 나타내자면

permutation([], [1, 2, 3, 4], 2) = permutation([1], [2, 3, 4], 1) + permutation([2], [1, 3, 4], 1) + permutation([3], [1, 2, 4], 1) + permutation([4], [1, 2, 3], 1) 이다.

 

백트래킹의 원리로 풀 수 있다.

종료 조건은 m이 0이 되거나 현재 탐색해야 하는 숫자의 길이보다 작을 때 종료된다.