[BOJ] N과 M (2)

---

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
ans = []

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

dfs(1)

결과

풀이 방법

• 백트래킹 문제이다.
• 백트래킹이란 문제를 해결해가다가 주어진 조건을 만족하지 않는다고 판단되는 경우 더 진행하지 않고 이전 단계로 다시 돌아가서 다른 방향으로 탐색하는 문제 해결 방법이다.
• 보통 DFS(깊이우선탐색)으로 구현하며 종료 조건을 갖는 재귀 구조를 갖는다.
• 이 문제의 경우 종료 조건은 수열의 길이가 m일 때이며, 종료한 후 수열에서 마지막 숫자를 pop하여 다른 숫자(dfs 함수 안 for문의 i)가 수열에 추가될 수 있도록 한다.

---