(BOJ) 15649. N과 M (1)

📗문제 설명

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

• 입력
  • 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
• 출력
  • 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.
    

💡문제 풀이 IDEA

1. 백트래킹. 반목문을 돌면서 숫자를 선택 ( 이때 방문 여부 확인)
2. 재귀에서 m개를 선택했을 경우 print해줌.
3. 이후 다시 pop하고 방문여부를 거짓으로 바꿈.

• 시간복잡도. N!까지 가능 (10까지.)

• 자료구조
  • int ( 결과값 저장)
  • boolean ( 방문여부)

👨🏻‍💻문제 풀이 CODE

import sys
input=sys.stdin.readline

N,M=map(int,input().split()) # N=숫자 갯수 , M=선택개수
rs=[]
ch=[False]*(N+1)

def recur(num):
    if num==M: # 선
        print(' '.join(map(str,rs)))
        return
    for i in range(1,N+1):
        if ch[i]==False:
            ch[i]=True
            rs.append(i)
            recur(num+1)
            ch[i]=False
            rs.pop()

recur(0)

'''
#0, N=4,M=2
1~N까지 반복문을 돈다.
ch[i]를 방문하지 않았다면 방문으로 바꾸고 결과에 추가한다. 
재귀하여서 num(선택된 갯수 확인)을 1 늘리고 다시 돈다. 
방문하지 않았다면 append [1]에서 [1,2]로 된다음 num이 2로 증가. M과 같기때문에 print한다.
그 다음 수([2])를 위해 미방문으로 바꾸고 pop한다.다 끝났다면 [1]로 돌아와서 [1]을 미방문으로 바꾸고 팝한다. 
반복문 실행. 

'''