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

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

15650번: N과 M (2)

아이디어

• 백트래킹을 이용
• road배열에 값을 넣으며 백트래킹을 진행하고 road의 길이가 m과 같아질 때 road 출력
• 백트래킹의 인자는 현재 숫자의 다음 숫자를 인자로 넘겨주어 그 수부터 다시 백트래킹을 진행하게 함
• 다시 돌아올 때에는 pop을 이용해 road를 다룸

import sys
input = sys.stdin.readline

def back(cnt):
    if len(road) == m:
        for i in road:
            print(i, end=" ")
        print()
        return
    for i in range(cnt, n):
        if (i+1)not in road:
            road.append(i+1)
            back(i+1)
            road.pop()  



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

road = []
back(0)

마무리

• N과 M (1)은 순열을 구하는 경우였지만 이 문제는 조합을 구해야 해서 처리를 또 해줘야 했다.
• 백트래킹의 반복되는 함수가 어떤 식으로 동작하는지 정확히 인지하고 있어야 나중에 어려운 문제를 풀 때 시간을 단축할 수 있다.
• 아직 백트래킹이 딱 뽝 짠 하고 나오는 수준이 아니라 더 연습하자.