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

문제 주소 및 출처 ❕

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

문제 : 15649 N과 M (1)

 

언어 : Python3

 

 

풀이 방법 1. Python 내장함수 itertools의 순열 이용

 

풀이 방법 2. 백트래킹 이용

 

 

💬 나의 코드

📌 Python3 👉 itertools 이용

import itertools

N, M = map(int, input().split())

arr = [x for x in range(1, N+1)]
v = itertools.permutations(arr, M)

for w in v:
    sub_a = ""
    for i in range(M):
        sub_a += str(w[i]) + " "
    print(sub_a)

 

📌 Python3 👉 백트래킹 이용

N, M = map(int, input().split())

visited = [0]*N
ans = []

def seq():
    if len(ans) == M:
        answer = ""
        for x in ans:
            answer += str(x) + " "
        print(answer)
        return
    
    for i in range(N):
        if visited[i] == 0:
            visited[i] = 1
            ans.append(i+1)
            seq()
            visited[i] = 0
            ans.pop(-1)

seq()

 

풀고 나서 보니, visited 없어도 될 듯!

if visited[i] == 0 대신에 if i+1 not in ans 도 괜찮을 것 같다,,