[Python] 백준 15666번 - N과 M (12)

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

15666번: N과 M (12)

 

혼자 힘으로 풀었는가? O

알고리즘 분류
 - 백트래킹

 

문제

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

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

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

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

출력

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

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

 

---

2023.03.14 - [Algorithm/백준] - [Python] 백준 15663번 - N과 M (9)

[Python] 백준 15663번 - N과 M (9)

 

위 문제와 비슷하다.

 

하지만 조금 다르다.

 

조건식만 조금 수정해주면 되었다.

 

풀이방법은 기존의 신박한 방법을 차용하여 풀었다.(기억해서 풀었음!)

 

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
arr = list(map(str, input().split()))
arr.sort(key=int)
stack = []

def dfs(index):
    if index == m:
        print(' '.join(stack))
        return
    tmp = -1
    com = -1
    if len(stack) > 0:
        com = int(stack[len(stack)-1])
    for i in range(n):
        if int(arr[i]) > int(tmp) and int(arr[i]) >= com:
            stack.append(arr[i])
            dfs(index+1)
            tmp = stack.pop()
dfs(0)

이번 문제는 저번문제와 다른 점은

 

같은 수의 중복출현이 가능하지만

 

출현해야 할 숫자는 앞의 숫자보단 크거나 같아야 한다.

 

위 조건만 충족시켜 주면 이전문제와 크게 다를 바가 없다.

 

기존 문제의 visited 변수가 사라진 대신 com의 비교변수가 추가된 것이다.