[Baekjoon] 15650번 : N과 M (2) (Python, 백트래킹, dfs)

[Baekjoon] 15650번 : N과 M (2) (Python, 백트래킹, dfs)

 

목차

 

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

15650번: N과 M (2)

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

Python

 

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

 

본 문제는 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

 

N과 M (1) 에서 다뤘던 문제의 연장선이다.

다만 고른 수열이 오름차순이 되도록 조건문을 추가하는 것을 기억해야한다.

 

 

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

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

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

 

방법 2 - 메모리 30864KB / 시간 16ms / 코드 길이 B

 

dfs parameter로 조절하는 방법 또한 존재한다.

 

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

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

    for i in range(init, n+1):
        if i not in s:
            s.append(i)
            dfs(i+1)
            s.pop()
dfs(1)