[백준/15649][파이썬] N과 M(1)

문제

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

15649번: N과 M (1)

풀이

백트래킹 연습 문제

출력할 때

print(' '.join(map(str, arr)))

을 사용할 수도 있는 듯 하다. 해당 코드는 아래에 ver2로 첨부하였다.

코드

import sys

read = sys.stdin.readline
n,m = list(map(int,read().split()))

#1~n까지 자연수 중 중복없이 m개를 고르는 수열
vis=[0 for _ in range(n+1)]
arr=[0 for _ in range(n+1)]
def choose(k): #현재까지 k개의 숫자를 선택
  if(k == m):
    for i in range(m):
      print(str(arr[i])+" ",end="")
    print()
  else:
    for i in range(n):
      if(vis[i] == 0):
        vis[i] = 1 #방문 표시
        arr[k] = i+1 #배열에 저장
        choose(k+1) #k+1번째 수 고르기
        vis[i] = 0
  
choose(0)

import sys

read = sys.stdin.readline
n,m = list(map(int,read().split()))

#1~n까지 자연수 중 중복없이 m개를 고르는 수열
#고른 수열은 오름차순

vis=[0 for _ in range(n+1)]
arr=[0 for _ in range(m)]
def choose(k): #현재까지 k개의 숫자를 선택
  if(k == m):
    print(' '.join(map(str, arr)))

  else:
    for i in range(n):
      if(vis[i] == 0):
        vis[i] = 1
        arr[k] = i+1
        choose(k+1)
        vis[i] = 0
  
choose(0)