[코딩테스트] 백준 15649번: N과 M (1)

1. 아이디어

▪ 선택한 숫자의 개수가 M이 되면 멈추고 출력

▪ 백트래킹으로 for문 돌리면서 방문하지 않은 숫자 선택

   - 방문여부 True로 갱신

   - 선택한 숫자 리스트에 추가

   - num+1 하고 재귀호출

   - 방문여부 False로 갱신

   - 선택한 숫자 리스트에 뺴기

2. 시간복잡도

▪ log(N!)

3.변수

▪ 방문여부: bool[]

▪ 선택한 숫자: int[]

Code

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
chk = [False] * (N+1)
rs = []

def back(num):
    if num == M:
        print(' '.join(map(str, rs)))
        return

    for i in range(1,N+1):
        if chk[i] == False:
            chk[i] = True
            rs.append(i)
            back(num+1)
            chk[i] = False
            rs.pop()

back(0)

 

15649번: N과 M (1)