[python] 15649번 N과 M (1)

1. 문제 링크 및 문제

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

1-1 문제 요약

: 1부터 까지 자연수 중에서 중복없이 M개를 골랐을 때의 경우의 수

2. 해결 방법 생각해보자 ...

중복없이 M개를 뽑는 모든 경우의 수를 구해야 함 == 백트래킹

3. 코드

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

def dfs(arr):
    if len(arr) == M :
        print(' '.join(map(str,arr)))
        return

    for i in range(1,N+1):
        if i not in arr :
            arr.append(i)
            dfs(arr)
            arr.pop()

dfs([])

dfs 함수 인자로 배열을 사용 arr = []
arr 에 i 가 없다면 추가 후 , dfs 다시 돌려돌려 , 길이가 M 이 됐을 때 arr.pop()

그림으로 이해

백준 예제 입력 2 (N=4, M=2 ) 입력하여 이해해보장

코드 마지막줄 dfs([ ]) 실행 시 , i=1 일 때 dfs([1]) 이 실행됨.

1. dfs([1]) 실행 시, i=2 일 때 dfs([1,2]) 실행됨.
   

2. dfs([1,2]) 실행 시, if len(arr)==M 을 만족하므로, print 1 2. return 을 하게 됨.
   그렇담 dfs([1]) 의 arr.pop() 으로 돌아감
   

전체그림 !!

N과 M 시리즈를 풀면서 백트래킹을 전보다는 더 잘 이해하게 되었다