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

 

문제 분석

• 자연수 N, M
• 1부터 N까지 자연수 중 중복 없이 길이가 M인 수열 
• 중복 x, 순서 o
• 순열

 

코드 설계

• 입력받고
• 1부터 시작하는 길이가 n인 list 생성
• 방문여부를 확인할 길이가 n이고 false값이 저장된 리스트 visited 생성
• def dfs() 
• 종료조건 : 답을 넣는 리스트가 m과 같아지면 return

 

정답 코드

import sys
input = sys.stdin.readline

n, m = list(map(int, input().split()))
ans = []

def dfs() :
    if len(ans) == m: # 재귀 : 종료조건
       print(' '.join(map(str, ans)))  # 리스트 ans의 모든 요소를 문자열로 변환 후, 공백으로 구분하여 하나의 문자열로 결합
       return

    for i in range(1, n+1):  # n번 반복
       if i not in ans:  # 만약 i가 ans 리스트안에 없으면
          ans.append(i)  # ans에 넣고
          dfs()  # 함수를 재귀적으로 호출해서 다음 깊이로 들어감
          ans.pop() #
dfs()

 

itertools

import sys
from itertools import permutations

input = sys.stdin.readline

n, m = map(int, input().split())
arr = [ i for i in range(1,n+1) ]

for i in permutations(arr, m) : 
    for j in i : 
       print(j, end = ' ')
    print()