백준 15650. N과 M(2)

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

15650번: N과 M (2)

NPM 중에서도 오름차순으로 정렬되어 있는 수열만 출력하는 문제. 수열을 만드는 문제들에서 주로 쓰이는 DFS(Depth First Search, 깊이우선탐색)를 사용했다.

기본적인 개념은 다음과 같다.

[1]에서 시작해서 두번째 숫자에 우선 1을 넣는다. [1,1] -> 끝자리에 1~9를 모두 넣어본다.

한칸 후퇴해서 [1,2] 로 리스트를 바꾼다. ->다시 끝자리에 1~9를 모두 넣어본다. ...

이런 식으로 끝단부터 계속 따져주는 방법.

오름차순 정렬의 경우에는 이전보다 큰 값만 들어가면 되므로, 값을 함수의 인자로 넘겨주고 반복문을 해당 값부터 돌렸다.

n,m = map(int, input().split())

arr = []

def dfs(val):
	if len(arr) == m:
		print(' '.join(map(str, arr)))
		return
	for i in range(val, n+ 1):
		if i not in arr:
			arr.append(i)
			dfs(i)
			arr.pop()

dfs(1)

아직 dfs가 어색한데, 연습을 좀 해야될듯.