[백준] 15654번: N과 M (5) (python)

15654번: N과 M (5)

---

문제 )

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

• N개의 자연수 중에서 M개를 고른 수열

 

 

입력 :

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

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

 

 

출력 :

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

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

 

 

 

 

 

 

풀이)

오랜만에 시작한 백트래킹 문제이다.

길이가 m인 수열을 모두 구하는데, n개의 자연수는 모두 다른 수이여야 하므로

visited를 사용해, 중복을 피해야겠다는 생각을 했다.

 

코드의 전문은 다음과 같다.

 

n, m = map(int, input().split())
# 입력으로 주어지는 수
arr = list(map(int, input().split()))
# 오름차순으로 출력해야하므로 정렬을 먼저 한다.
arr.sort()
 
# 출력을 위한 리스트를 먼저 만들어 두었다.
li = [0] * m
# 중복을 피하기 위한 visited 변수이다.
visited = [False] * n
 
def recur(cur):
    # 재귀가 m번째에 도달했을 때 체크
    # == m자리 수열이 만들어졌을 때
    if cur == m:
        print(*li)
        return
 
    # 수열에 담길 수
    for i in range(n):
        # 이미 사용한 수라면 continue
        if visited[i]:
            continue
        
        # 리스트에 수를 담고 방문체크
        li[cur] = arr[i]
        visited[i] = True
 
        # 다음 재귀로 들어간다.
        recur(cur + 1)
        # 다른 재귀를 위해, 초기화를 해준다.
        visited[i] = False
 
recur(0) # 0부터 출발함.
 

 

다른 백트래킹 문제들도 이 문제처럼 좀 잘 풀렸으면 좋겠다.

---

출처 : https://www.acmicpc.net/problem/15654

15654번: N과 M (5)