백준 15651번 문제 바로가기

product을 이용한 풀이

N과 M (1)은 순열(permutation), N과 M(2)이 조합(combination)이었다면, 이번 문제 **N과 M (3)**은 중복순열(permutation with repetition)문제이다. 아마 4탄은 중복조합이 아닐까 추측해본다. 갓python은 중복조합과 중복순열에 대한 라이브러리도 가지고 있었으니… 바로 product이다.

# 입력
import sys
from itertools import product
n,m = map(int, sys.stdin.readline().split())
arr = [i+1 for i in range(n)]

# 처리
for ans in product(arr, repeat=m):
    print(*list(ans))

backtracking을 이용한 풀이

중복순열도 backtracking을 이용해서 풀어보자! 간단하게 순열 풀이에서 for문만 지우면 된다ㅎㅎ

# 입력
import sys
n,m = map(int, sys.stdin.readline().split())
ans = []

# 처리
def backtrack():
    if len(ans) == m:
        print(*list(map(str, ans)))
        return
    for i in range(1, n+1):
        ans.append(i)
        backtrack()
        ans.pop() # return이 실행되면 여기로 돌아옴. (전 단계로 돌아감 = backtrack)

backtrack()