[Python] Baekjoon - 15664. N과 M (10)

백준의 N과 M 시리즈는 N개의 숫자가 포함된 수열에서 M개를 고르는 문제이다. 매번 조건이나 규칙이 변경되어 총 12개의 문제가 있다. 이번 문제는 비 내림차순으로 출력하는 문제이며 백트래킹을 이용하여 풀 수 있다. 난이도는 실버 2이다.

 

백준 15664번 N과 M (10) 문제 정보

알고리즘 분류

- 백트래킹

난이도

- 실버 2

 

N과 M (10) 문제 요약

N개의 중복 수열 중 M개를 뽑아 비 내림차순 수열로 만드는 경우의 수를 모두 출력하는 문제다.

 

문제 풀이 과정

1. 수열에 포함된 숫자들의 중복을 제거하고 정렬하여 가지고 있는 리스트와, 각 숫자의 등장 횟수를 저장하는 리스트를 준비한다.
2. dfs를 이용해 작은 숫자부터 방문하거나/방문하지 않으면서 M개의 숫자를 선택한다. 이때, 선택되는 숫자의 등장 횟수를 1 빼서 등장 횟수가 0 이상인 숫자만 선택 가능하도록 한다.

 

코드

코드 설명

• num_list: 수열에 포함된 숫자들의 중복을 제거하고 정렬하여 가지고 있는 리스트
• num_cnt: 각 숫자의 등장 횟수를 저장하는 리스트
• selected: 현재 상태에서 선택된 숫자들의 리스트

N, M = map(int, input().split())
num_list, num_cnt, selected = [], [], []

pre = None
for num in sorted(list(map(int, input().split()))):
    if pre is None or pre != num:
        num_list.append(num)
        num_cnt.append(1)
    else:
        num_cnt[-1] += 1
    pre = num


def dfs(depth):
    # M개 선택되면 출력
    if len(selected) == M:
        for n in selected:
            print(n, end=' ')
        print()
        return

    # M개 선택 안했는데 숫자 남은거 없으면 종료
    if depth >= len(num_list):
        return

    # 이번 숫자 선택
    if num_cnt[depth] > 0:
        num_cnt[depth] -= 1
        selected.append(num_list[depth])
        dfs(depth)
        num_cnt[depth] += 1
        selected.pop()

    # 이번 숫자 선택 X
    dfs(depth+1)

dfs(0)