[백준BOJ] 15666번 N과 M(12).py

 

백준 저지에서 N과 M(12)를 파이썬을 통해 풀어 보았다. 

 

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

15666번: N과 M (12)

 

15666번 N과 M(12).py

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

 

15666번 N과 M(12)

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- N개의 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.
- 고른 수열은 비내림차순이어야 한다.
- 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

설명

조건에 맞는 수열들을 출력해야 한다. N개의 수가 중복될수도 있게 주어지는데 주어지는 각 숫자의 개수와 사용할 수 있는 숫자의 개수는 전혀 관련이 없어서 set을 통해 주어진 숫자가 하나씩만 남도록 했다.

 

M크기의 배열에 대해서 각 자리마다 올 수 있는 모든 경우의 수를 찾아야한다. 배열에 숫자를 추가하려면 아예 빈배열이거나 가장 뒤에 있는 숫자보다 같거나 커야한다. 이러한 조건을 배열의 크기가 M까지 1씩 커질 때마다 수행한다.

 

즉 백트래킹을 이용해서 문제를 해결할 수 있다. 

 

추가로 최근에 파이썬에도 main함수를 계속 넣어주면 풀었는데 이제 다시 main 함수를 빼고 풀 계획이다. 그게 더 파이썬스러운 것 같다.

코드

#15666번 N과 M(12)
def sol(depth) :
  if depth == m : 
    print(" ".join(map(str,arr)))
    return 

  for i in range(len(nums)):
    if depth == 0 or arr[-1]<=nums[i] : 
      arr.append(nums[i])
      sol(depth+1)
      arr.pop()

n,m = map(int,input().split())
nums = sorted(list(set(map(int,input().split()))))

arr= [] 
sol(0)