[백준] 15650

N과 M (2)

문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

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

출력

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

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

풀이

let arr;
let n;
let m;

const recurNandM = (k, l, ans) => {
  if (l > n + 1) return;
  if (k === m) ans.push(arr.join(" "));
  else {
    for (let i = l; i <= n; i++) {
      arr[k] = i;
      recurNandM(k + 1, i + 1, ans);
    }
  }
};

const nAndM = () => {
  [n, m] = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split(" ")
    .map(Number);
  let ans = [];
  arr = Array.from({ length: m }, (v) => 0);
  recurNandM(0, 1, ans);
  console.log(ans.join("\n"));
};

nAndM();

반성회

15649 의 파생문제 답게 거의 비슷한 구성을 보이나, 숫자가 사전순으로 증가한다는 차이점이 있다

따라서 반복문을 돌 때 이전에 사용했던 숫자보다 1 큰 수부터 탐색하며, 어차피 이전에 사용했던 숫자들보다 큰 숫자만을 탐색하므로 숫자가 중복될 일이 전혀 없어 isUsed 배열을 사용하지 않는다

• arr : M자리의 수열을 저장하는 배열, 재귀를 들어갈 때마다 특정 자리수 (k) 에 숫자를 채워넣는다
• k : 수열의 몇 번째 자리를 계산하는지 나타내는 자리수
• l : 직전에 수열에 채워넣었던 숫자 (i) 보다 1 큰 수, 다음 재귀에서 반복문은 i = l부터 시작한다
• ans : 나중에 수열을 한꺼번에 출력하기 위해 만든 수열을 저장하는 배열

재귀 진행 순서

1. k는 자리수를 나타내고, 0번째 자리부터 채워나가므로 recurNandM의 인자 k는 0으로 설정
2. l은 재귀함수 내의 반복문에서 반복자 i의 시작점이므로 1로 설정
3. recurNandM의 탈출조건은 두 종류가 있다
   1. l이 n + 1보다 클 때 : i의 범위가 1부터 n까지이므로 l의 범위는 1부터 n + 1까지이고, 따라서 l이 n + 1보다 커지면 더이상 수열에 채울 수 있는 숫자가 없으므로 재귀를 탈출한다
   2. k가 m일 때 : k는 0부터 시작하여 m개 자리를 채우므로 k의 최대값은 m - 1이고, 따라서 k가 m일 땐 원하는 수열의 길이보다 길어지므로 지금까지 만든 수열을 ans에 push하고 재귀를 종료
4. 위의 두 경우에 해당되지 않을 경우, k번째 자리에 값을 채워넣기 위해 반복문을 돈다
   1. 반복문의 반복자 i는 l부터 n까지 돈다(직전에 채워넣었던 수보다 1 큰 수부터 채워넣어야 오름차순이 되므로 l부터 n까지의 수가 올 수 있다)
   2. 수열의 k번째 자리에 i를 채워넣는다 (arr[k] = i)
   3. k번째 자리에 i를 사용했으므로, 그 뒤에 오는 자리는 무조건 i보다 커야 하므로 다음 재귀의 인자 l에 i + 1을 넣는다
   4. 또한 k번째 자리를 채워넣었으므로 k + 1번째 자리를 채워넣기 위해 다음 재귀의 인자 k에 k + 1을 넣는다
   5. 재귀를 빠져나온다는 건 k번째 자리에 i를 넣는 모든 오름차순 수열을 완성하였거나, l이 n + 1보다 커 사용할 수 있는 숫자가 없다는 것을 의미하므로, 탐색을 중지한다
5. 모든 재귀를 빠져나와 recurNandM을 종료하고 nAndM 함수로 돌아왔다는 것은 모든 경우의 수를 탐색하여 가능한 수열을 전부 찾아냈다는 뜻이므로, ans에 저장된 모든 수열을 \n을 기준으로 구분하여 출력한다