접근
1부터 N까지의 수 중 M개를 고른 수열을 오름차순으로 출력해야 한다.
우선 재귀를 통해 풀 수 있겠다는 생각이 들었다. 그리고 간만에 구현해보는 DFS에 정신이 아득해질 무렵 작동하는 코드를 만들어낼 수 있었다(...).
코드
from sys import stdin
N, M = tuple(int(i) for i in stdin.readline().split())
def search(answer, depth, next_idx):
global N, M
if depth == M:
print(" ".join(answer))
return
for i in range(next_idx, N + 1):
answer += str(i)
search(answer, depth + 1, i + 1)
answer.pop()
search([], 0, 1)일반적인 DFS에서 쓰는 방문 여부 배열은 이 문제에서는 쓸 필요가 없었다. 원 데이터가 사전순으로 이미 정렬되어 있어 다음 탐색 범위를 조정하는 것 만으로 중복 탐색을 방지할 수 있기 때문이라 할 수 있다.
백트래킹 문제는 아직 많이 풀어보지 않아서 그런건지, 이것과 DFS의 차이점이 무엇인지 의문이 들어 좀 알아보았다. 구현만 보면 사실상 똑같지만 문제 풀이 전략 수립시 관점이 약간 다른 것 같다. 호주를 오스트레일리아라고도 부르는 것과 비슷한 느낌이라 해야 할까?...
