문제

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

아이디어

• 이전 문제인 https://velog.io/@kimjaeseop/BOJ-15649-N과-M-1 와 거의 유사하다
• 오름차순으로만 출력되게 바꾸면 된다.
• 백트래킹 알고리즘으로 중간에 정답이 될 가능성이 없는 노드들은 제거하면서 진행했다.

코드

N, M = map(int, input().split())

def func(depth, lst):
    if depth == M-1:
        print(*lst)
        return

    if N-max(lst) < M-(depth+1): # 유망하지 않은 노드 제거
        return

    for i in range(max(lst)+1, N+1): # 오름차순이기 때문에 가장 큰 값 다음 값부터 시작
        if i not in lst:
            lst[depth+1] = i
            func(depth+1, lst)
            lst[depth+1] = 0

for i in range(1, N+1):
    arr = [0 for _ in range(1, M+1)]

    arr[0] = i
    func(0, arr)

리뷰

• 코드에 손 대기 전까지는 반복문만으로 풀 수 있을 줄 알았는데 아직 구현 능력이 부족한 것 같다.
• 유망하지 않은 노드를 제거하는 부분이 백트래킹에서 중요하다.

GIT

• https://github.com/Kimjaeseop/acmicpc/blob/master/15650/15650.py