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

15650번: N과 M (2)

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

is_used = [False]*(n+1)

temp = []
answer = []

def back(start):
    
    if len(temp) == m:
        answer.append(' '.join(map(str,temp)))
        return
    for i in range(start,n+1):
        if i not in temp:
            temp.append(i)
            back(i+1)
            temp.pop()

back(1)

for ans in answer:
    print(ans)

이번 문제는 바로 이전에 풀이했던 15649번의 응용 문제이다.

[백준 15649번] N과 M(1)

이 문제를 처음 풀이했을 때는 백트래킹을 사용하지 않고 집합으로 저장을 하여 중복된 경우를 정답(answer) 리스트에 넣지 않았는데, 이 문제의 의도는 이것이 아니었다.

 

이 문제에서 의도한 바는 '오름차순'으로 저장해야 한다는 것이므로 현재 수보다 낮은 수들은 사전에 방문하지 않는 방식으로 풀어야 한다. 따라서 start 라는 매개변수를 만들어서 반복문의 시작점으로 삼아 사전에 탐색하지 않도록 가지치기(pruning) 하였다.