[백준 6603] 로또

문제

https://www.acmicpc.net/problem/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가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

아이디어

각 테스트 케이스에 포함된 원소 중에서 6개를 뽑는 조합의 수를 구하는 문제이다.

테스트 케이스로 들어온 원소를 오름차순으로 정렬해서 배열에 저장한다.
모든 테스트 케이스마다 순회하면서, 해당 테스트 케이스에 포함된 원소를 6개 뽑는 경우를 구한다.
이 때 console.log() 로 출력할 때 오버헤드를 줄이기 위해서 한 번만 호출하기 위해서 구한 조합은 answer 배열에 넣는다.
answer 배열에 들어간 순서대로 출력한다.

소스 코드

// 입력 처리
const INPUT_NAME = 'i1.txt';
const filePath = process.platform === 'linux' ? '/dev/stdin' : `./boj/${__dirname.split('\\').pop()}/${INPUT_NAME}`;

const input = require('fs')
  .readFileSync(filePath)
  .toString()
  .trim()
  .split('\n')
  .map(item => item.trim());

const cases = input
  .filter((_, i) => i < input.length - 1)
  .map(
    str =>
      str
        .split(' ')
        .filter((_, i) => i > 0) // 맨 첫번째 수는 k를 나타내는 숫자이니 제외
        .map(e => Number(e))
        .sort((a, b) => a - b) // 사전순 정렬
  );

// 풀이
function solution() {
  const answer = [];

  function combination(arr, r) {
    const result = Array.from({ length: r }, () => 0);

    const dfs = (depth, begin) => {
      if (depth === r) {
        answer.push([...result]);
        return;
      }

      for (let i = begin; i < arr.length; i++) {
        result[depth] = arr[i];
        dfs(depth + 1, i + 1);
      }
    }

    dfs(0, 0);
  }

  // 각 테스트 케이스마다 6개의 원소를 뽑는 조합의 수를 구한다.
  cases.forEach(arr => {
    combination(arr, 6);
    answer.push([]); // 테스트 케이스 사이에 빈 줄을 출력하기 위함
  });

  console.log(answer.map(arr => arr.join(' ')).join('\n'));
}

// 실행
solution();