[#15650] N과 M(2)

문제

#15650 N과 M(2)
Silver4
적용 알고리즘: 백트래킹 알고리즘

---

풀이 방법

• 15649 문제와 동일한데 조건만 추가해주면 된다.
• 사전순으로 숫자가 arr에 담기기 때문에 arr의 가장 마지막 원소와 현재 추가하려는 수를 비교하여 현재 추가하려는 수가 arr[-1] 원소보다 클 때만 append 하면 된다.

코드 흐름

• 15649 문제와 거의 유사하기 때문에 생략.

코드

def dfs():
    if (len(arr) == m):
        print(" ".join(map(str, arr)))
        return
    for i in range(1, n + 1):
        temp = 0
        if (len(arr) != 0):
            temp = arr[-1]
        if (len(arr) == 0 or temp < i):
            arr.append(i)
            dfs()
            arr.pop()


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

dfs()

체감 난이도: 3.6/5
그래도 이전 문제 하나 풀었다고 이해는 된다…