[백준 15650] N과 M(2)

문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

• 고른 수열은 오름차순이어야 한다.

입력

첫째 줄에 N과 M이 주어진다.

1 ≤ M ≤ N ≤ 8

 

출력

한 줄에 선택한 M개의 수를 출력한다.

중복으로 출력할 수 없고 오름차순으로 출력한다.

---

접근

백트래킹으로 1차원 리스트에 저장된 수열을 M개 선택하도록 하였다.

 

구현

다음은 N개의 수열 중에서 M개를 선택하는 함수이다.

선택된 수는 picked라는 리스트에 저장하게되며 리스트의 길이가 M이 되었을 때 리스트 안에 있는 수를 출력한다.

만약 아직 M개를 선택하지 못했다면 선택하지 않은 수들을 골라 리스트에 넣어주고 재귀호출을 한다.

def select(next, picked):
    if len(picked) == M:
        print(*picked)

    for idx in range(next, N):
        if not visited[idx]:
            visited[idx] = True
            picked.append(numbers[idx])
            select(idx+1, picked)
            visited[idx] = False
            picked.pop()

---

전체 코드

def select(next, picked):
    if len(picked) == M:
        print(*picked)

    for idx in range(next, N):
        if not visited[idx]:
            visited[idx] = True
            picked.append(numbers[idx])
            select(idx+1, picked)
            visited[idx] = False
            picked.pop()

N, M = map(int, input().split())
numbers = [n+1 for n in range(N)]
visited = [False for _ in range(N)]

select(0, [])