졍's 기술 블로그

N과 M (3)

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 512 MB
알고리즘 분류 : 백트래킹

문제

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

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

입력

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

출력

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

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

예제 입출력

Algorithm

itertools library 이용
1. product(중복 순열) 이용해 모든 조합 만들기
2. 리스트 정렬 후 출력

백트래킹 사용
1. for문을 돌면서 stack에 숫자 추가하고 재귀함수 호출
2. 재귀함수 return되면 pop
3. stack의 길이가 M이 되면 stack print

Code

# itertools library
from itertools import product

def use_product():
    nums = list(product(range(1, N+1), repeat = M))
    nums.sort()
    for num in nums:
        print(' '.join(list(map(str, num))))
        
N, M = map(int, input().split())
use_product()

메모리: 115200 KB
시간: 1504 ms

# back tracking - 재귀
def back_tracking():
    
    # stack 길이가 M이 되면 print
    if len(stack) == M:
        print(' '.join(list(map(str, stack))))
    else:
        # 1부터 N까지 순서대로 stack에 append
        for num in range(1, N+1):
            stack.append(num)
            # 재귀함수 호출
            back_tracking()
            # 재귀함수 return되면 pop
            stack.pop()
            
N, M = map(int, input().split())
stack = []
back_tracking()

메모리: 30864 KB
시간: 1504 ms