[ BOJ 15649 ] N과M(1) (Python)

문제

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

• 1부터 N까지 자연수에서, 중복 없이 M개를 고른 수열을 오름차순으로 출력하면 된다.
• 놀랍게도 이미 푼 문젠데 기억에서 삭제됐다.

문제 풀이

1. 이전에 출력된 숫자인지 확인을 해줄 배열 checklist, 출력할 숫자 배열 result을 만든다.
2. result의 0번째 배열부터 m-1번째까지 순차적으로 채워줄 것이다.
3. dfs 함수의 인자는 (index, n, m) 이다.
   • index가 0부터 1씩 증가하면서, m이 되는 순간 result에 저장된 요소들을 출력한다.
   • 숫자를 출력하고 나면 check_list의 값을 1로 바꾼다.
4. check_list의 값이 1이면 이미 출력됐다는 의미이므로 무시한다.
5. check_list의 값이 0이면, result_list에 숫자를 넣는다.
6. 숫자를 출력했다고 check_list에 체크해준 뒤, index를 1 증가시켜서 dfs 함수에 넣는다.
7. ⭐️ dfs 함수가 종료된 뒤 check_list 체크 해제를 한다.
   그래야 다음 숫자가 체크를 할 수 있다!

코드

import sys

n,m= map(int, sys.stdin.readline().rstrip().split())
check_list=[0]*(n+1)
result_list=[0]*(m)

def check(index,n,m):
    if index==m:
        for i in range(m):
            print(result_list[i],end=" ")
        print()
        return

    for i in range(1,n+1):
        if check_list[i]==1: #이전에 출력된 숫자이면 무시
            continue
        result_list[index]=i #해당 인덱스에 숫자 넣어줌
        check_list[i]=1      #출력된 숫자 체크

        check(index+1,n,m)   #다음숫자 출력
        check_list[i]=0      #초기화

check(0,n,m)