[백준] 15651번 N과 M(3)

www.acmicpc.net/problem/15651

15651번: N과 M (3)

 

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

 

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

 

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

 

풀이

중복 순열의 경우에는 이전 글에서 설명은 안했지만 itertools의 product라는 기능을 이용하면 쉽게 풀 수 있다.

itertools product이용

import sys
import itertools

N, M = map(int, sys.stdin.readline().split())
N_list = [i for i in range(1, N + 1)]

answer = list(itertools.product(N_list, repeat=M))

for i in answer:
    print(' '.join(map(str,i)))

product에 인자로 원하는 list를 입력하면 해당 list를 반복해서 만든 중복 순열이 생성된다.
repeat 변수를 조절하는 것으로 한 항목을 몇 번 사용할지 정할 수 있다.
itertools.product(list1, list2, list3)와 같이 다양한 리스트를 변수로 넘길 수 있다.

출력을 join을 이용하여 구현하였다.
뒤에오는 데이터를 join 앞에 있는 구분자로 구분하여 합치는 것이다.
map을 이용하여 list 안의 데이터만 str형으로 변경하여 출력하였다. 

 

재귀 이용

import sys

N, M = map(int, sys.stdin.readline().split())
answer = []

def NandM3(index, N, M):
    if index == M :
        print(' '.join(map(str, answer)))
        return
    
    for i in range(N):
        answer.append(i+1)
        NandM3(index+1, N, M)
        answer.pop()
        
NandM3(0, N, M)

1번에서 구현한 부분에서 중복인지 확인하는 check에 대한 부분만 제거하면 재귀로도 쉽게 구현할 수 있다.