백준 알고리즘 15642 (N과 M(4)) - python

백준 알고리즘 15642 (N과 M(4)) - python

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

15652번: N과 M (4)

 

N과 M 문제에서 같은 수 여러번 골라도 되며, 

비내림차순을 만족해야한다.

 

[문제 풀이]

1. DFS 함수 정의 (depth, i (초기값 1))

2. depth == M 탈출 조건, tmp를 join하며 출력

3. 비내림차순은 다음 depth에서 i 이상을 지정해야함 

 -> for문이 i부터 시작되게 함

4. tmp에 j를 append하고 depth를 늘리며 DFS 진행

5. 백트래킹

 

import sys

def DFS(depth, i):
    if depth == M:
        print(' '.join(map(str, tmp)))
    else:
        # for문이 다음 depth에서 i이상(비내림차순)
        for j in range(i, N+1):
            tmp.append(j)
            DFS(depth+1, j)
            tmp.pop()
    return

if __name__ == '__main__':
    N, M = map(int, sys.stdin.readline().split())
    tmp = []
    DFS(0, 1) # depth, i 초기값 1