[백트래킹] BOJ 15650번 : N과 M(2)

문제

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

풀이

• 앞서 풀었던 15649번의 풀이와 유사한 문제이다.
• 15649번은 각 자리 간의 숫자 배치에 대해 중복되지만 않으면 아무런 제약이 없지만, 이 문제에서는 앞 자리 숫자들보다 새로 올 숫자의 크기가 항상 커야 한다.
• 기존 코드에서 한 가지만 추가하면 된다. 다음에 올 숫자를 구할 때, 앞에 왔던 숫자의 +1 한 값부터 가지고 오면 된다.
• back 함수에 매개변수 start 값을 받아 start ~ N+1까지의 숫자를 추가하는 형식으로 코드를 구현하였다. 이 때 start에는 i+1 즉, 앞서 추가한 숫자+1의 값을 대입한다.

코드

# N과 M(2)

N, M = map(int, input().split())
ans = []

def back(start):
    # 출력
    if len(ans) == M:
        print(" ".join(map(str, ans)))
        return
    # 숫자 배열 생성
    for i in range(start, N+1):     # 앞에서 사용한 숫자보다 큰 숫자만 사용해야 함
        if i not in ans:
            ans.append(i)       # i를 숫자 배열에 입력
            back(i+1)              # 앞서 입력한 i보다 큰 숫자만 가지고 숫자 배열을 완성해야 함
            ans.pop()

start = 1
back(start)