[15650] N과 M (2) / 파이썬

문제

시간제한 / 메모리 제한

입/출력

예제

알고리즘 분류

백트래킹

 

풀이

• 일단 파이썬의 순열 라이브러리를 사용해서 nPm의 목록을 구했다.
• 각 항목들이 튜플로 나오는데, 이를 리스트로 바꿔 주었다.
• 중복된 수열을 출력하면 안되고 오름차순으로 출력해야 하기 때문에 각 수열이 오름차순으로 증가하는 형태이면 print 해주었다.

 

코드

import sys
from itertools import permutations

N, M = map(int, input().split())
numbers = [i for i in range(1, N+1)]
permu = list(permutations(numbers, M))
result = [0 for _ in range(len(permu))]

for i in range(len(permu)):
    result[i] = list(permu[i])

for j in result:
    if j == sorted(j):
        print(*j)

 

새로 알게 된 점

순열이라는 굉장히 오래전에 어디선가 한번 들어봤던 것 같은 개념을 다시 배웠다.

순열이란 서로 다른 n개 중에서 r개를 중복없이, 순서에 상관있게 선택하는 것이다.(출처: 나무위키)

​위 두 가지 수식으로 나타낼 수 있다.

조합은 n개 중에서 r개를 순서 상관 없이 선택하는 것이다.

 

튜플은 sort가 안된다. 그래서 귀찮지만 리스트로 바꿔 주어야 한다.

 

좀 더 좋은 코드가 있을것 같다. 찾아보고 리팩토링 해봐야겠다.