[Baekjoon] 15652번 : N과 M (4) (Python, 백트래킹)

[Baekjoon] 15652번 : N과 M (4) (Python, 백트래킹)

 

목차

 

 

 

 

https://www.acmicpc.net/problem/15652

15652번: N과 M (4)

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

방법 1 - 메모리 30840KB / 시간 92ms / 코드 길이 282B

 

본 문제는 N과 M 시리즈 - 백트래킹 문제다.
15649번 N과 M (1) : https://aigong.tistory.com/427
15650번 N과 M (2) : https://aigong.tistory.com/428
15651번 N과 M (3) : https://aigong.tistory.com/475
15652번 N과 M (4) : https://aigong.tistory.com/476
15654번 N과 M (5) : https://aigong.tistory.com/480
15655번 N과 M (6) : https://aigong.tistory.com/481
15656번 N과 M (7) : https://aigong.tistory.com/482
15657번 N과 M (8) : https://aigong.tistory.com/483
15663번 N과 M (9) : https://aigong.tistory.com/484
15664번 N과 M (10) : https://aigong.tistory.com/485
15665번 N과 M (11) : https://aigong.tistory.com/486
15666번 N과 M (12) : https://aigong.tistory.com/487

 

 

• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

 

이 조건만 추가로 부합하도록 진행한다. 

 

import sys

def dfs():
    if len(t) == m:
        print(' '.join(map(str, t)))
        return

    for i in range(1, n+1):
        if len(t) == 0 or t[-1] <= i:
            t.append(i)
            dfs()
            t.pop()

n,m = map(int, sys.stdin.readline().split())
t = []
dfs()