[백준] 15652 - N과 M

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

15652번: N과 M (4)

문제 한줄 이해

-1부터 N까지의 숫자 중에서 M개를 뽑아 겹치지 않는 수열 출력

 

생각난 풀이

1번째 방법: 백트래킹이 생각나 재귀를 통한 DFS를 사용했다.

이때 재귀함수를 실행할때 인자를 현재 i값을 통해 넘어줬다.

-> why? 문제에서 우선 같은 수를 여러번 골라도 된다고 한다. 그렇다는건 현재 선택된 수가 다시 담겨도 된다는 뜻이기 때문이다.

예를 들어 4 2 예제일때 함수실행 순서는 다음과 같다.

dfs(1) 리스트[] -> dfs(1) 리스트 [1] ->dfs(1) 리스트[1,1] 길이가 2이므로 종료 그렇담 다시 마지막 dfs(1)이 실행된 지점으로 돌아간다.

이와 같은 과정을 반복하면서 넣었던 값을 다시 빼주고 탐색을 진행하는 것이다. 

이해가 되지 않을때는 종이에 직접 스택에 담으면서 천천히 따라가는걸 추천한다!

import sys
n, m  = map(int,sys.stdin.readline().split())
def back(start):
    if len(result) == m:
        print(*result)
        return
    
    for i in range(start,n+1):
        result.append(i)
        back(i)
        result.pop()
result = []
back(1)