[백준][Python] 15650번 N과 M (2)

15650번: N과 M (2)

 

 

코드

n, m = map(int,input().split())
s = []
visit = [False] * (n+1)
def dfs():
	if len(s) == m:
		print(*s)
		return
	
	for i in range(1,n+1):
		if visit[i] == False:
			if s:
				if s[-1] < i:
					visit[i] = True
					s.append(i)
					dfs()
					s.pop()
					visit[i] = False
			else:
				visit[i] = True
				s.append(i)
				dfs()
				s.pop()
				visit[i] = False
dfs()

N과 M(1) 문제와 비슷하지만 이 문제에서는 [3,1]과 같이 내림차순인 수열은 출력하면 안된다.

 

처음 풀었을 때는 s에 만약 숫자가 있다면 그 숫자보다 i가 작은 경우는 제외했다. s가 비어있다면 아무 숫자나 들어갈 수 있으므로 (1) 때와 같이 추가를 해줬다.

 

n, m = map(int,input().split())
s = []
visit = [False] * (n+1)

def dfs(num):
	if len(s) == m:
		print(*s)
		return
	
	for i in range(num,n+1):
		if visit[i] == False:
			visit[i] = True
			s.append(i)
			dfs(i+1)
			s.pop()
			visit[i] = False

dfs(1)

다른 사람들의 풀이를 참고했는데 dfs 함수에 앞의 숫자를 인자로 전달하여 for문의 범위를 앞의 숫자보다 1만큼 큰 수부터 n+1까지로 했다.