[백준] 6603

로또

문제

독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

풀이

let k;
let s;
let arr;
let ans = [];
let ansOne = [];
let input;

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

const lottery = () => {
  input = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split("\n")
    .map((n) => n.split(" ").map(Number));
  const len = input.length;
  for (let i = 0; i + 1 < len; i++) {
    k = input[i][0];
    s = input[i].slice(1);
    arr = Array.from({ length: 6 }, (v) => 0);
    recurLottery(0, 0);
    ans.push(ansOne.join("\n"));
    ansOne = [];
  }
  console.log(ans.join("\n\n"));
};

lottery();

반성회

테스트케이스가 여러 개가 들어올 수 있기 때문에 메인 함수 (lottery()) 에서 for문을 통해 테스트케이스마다 백트래킹을 작동시켰다

또한 백트래킹을 진행하는 재귀함수에선 인자로 로또 조합에서의 인덱스 뿐만 아니라 다음 반복문에서의 i의 최소값도 받아와 무조건 오름차순으로 번호를 뽑도록 하였다

무조건 6개의 숫자만 뽑으면 되기 때문에 재귀가 그렇게 깊지 않아 속도제한이 넉넉함