[BOJ / Node.js] 15666. N과 M(12)

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

15666번: N과 M (12)

문제

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

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

입력

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

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

출력

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

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

예제 입력 1

3 1
4 4 2

예제 출력 1

2
4

 

Solve

• 제공된 숫자들의 각각 갯수에 상관없이 사용할 수 있기 때문에, 미리 중복을 제거하였습니다.
• 비내림차순(길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.)의 조건을 만족하기 위하여 함수에 이전 값을 저장하기 위한 prev argument를 설정하였고, 이전 값과 비교하여 현재값이 작다면 탐색범위에서 제외되기 때문에 가지치기를 해주었습니다.

Code

const [input1, input2] = require("fs")
  .readFileSync(__dirname + "/input.txt")
  .toString()
  .trim()
  .split("\n")
  .map((el) => el.trim());

const [n, m] = input1.split(" ").map((el) => +el);
const values = [...new Set(input2.split(" ").map((el) => +el))];
values.sort((a, b) => a - b);
const answer = [];

const dfs = (v, arr, prev) => {
  if (values[v] < prev) return;
  if (arr.length === m) {
    answer.push(arr);
    return;
  }

  for (let i = 0; i < values.length; i++) {
    dfs(i, [...arr, values[i]], values[v]);
  }
};

dfs(0, [], 0);

console.log(answer.map((el) => el.join(" ")).join("\n"));