[BOJ #15650] N과 M(2)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

 

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

내가 쓴 코드

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

def n_m(k):
    if len(path) == M:          # len(path)
        print(*path)
        return
    for i in range(k, N + 1):   # range를 k부터
        if i not in path:
            path.append(i)
            n_m(i + 1)          # k+1이 아닌 i+1
            path.pop()

n_m(1)

어 어지럽다... 오늘 실습 문제보다 오늘 배웠던 내용이랑 비슷한 문제였다..! 그래서 비슷하게 풀면 되겠지 하고 쉽게 생각했는데.... 아 여기에 조건을 주기가 생각보다 어려웠다..ㅎㅎ 그래서 좀 찾아보면서 해결!! 

나는 k를 기저조건 if문에 쓰려고 만든 변수였는데, 그럴 필요가 없었다. 기저조건은 그냥 스택인 path의 len()값으로 하면 됨. 그리고 k를 1부터 받아와서, for문의 range 시작 범위로 지정해준다. 그리고 그 안에 재귀호출 시에 값을 바꿔줌. 처음에 i+1로 안쓰고 k+1로 써서 틀렸다. 뭐지? 뭐가 틀렸지 했는데.. 이걸 확인 안하고 제출하다니,,^^  그래서 정리를 해보자면,

조건1. 중복 없는 수열 -> 백트래킹 코드에 있는 for문 안에 if i not in path 조건문 추가
조건2. 오름차순 수열 -> 변수 k를 for문 range 시작 값으로 주기, 재귀 호출 시 함수 인자 값에 k+1가 아닌 i+1

 

출력 결과

 

제출 결과