[알고리즘/백준/5568] 카드 놓기(Nodejs, 완전탐색)

문제

---

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

5568번: 카드 놓기

 

풀이

---

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let [n, k, ...cards] = fs.readFileSync(filePath).toString().trim().split("\n");
const [N, K] = [n, k].map(Number);

const nums = [];
const ch = Array.from({ length: 100 }).fill(0);
let cnt = 0;

// 각 숫자 개수
for (let i = 0; i < cards.length; i++) {
  if (ch[cards[i]]) continue;
  ch[cards[i]] = cards.filter((card) => card === cards[i]).length;
}

function DFS(L, num) {
  if (L === K) {
    if (!nums.includes(num)) {
      cnt++;
      nums.push(num);
    }
  } else {
    // 정수 만들기
    for (let i = 0; i < N; i++) {
      const nx = cards[i];
      if (ch[nx]) {
        ch[nx] -= 1; // 사용 O
        DFS(L + 1, num + nx);
        ch[nx] += 1; // 사용 X
      }
    }
  }
}

DFS(0, "");
console.log(cnt);

 

---

 

카드 n개 중 k개를 선택해 만들 수 있는 정수의 개수를 구하는 문제이다. 이때 [1, 2, 12, 1]과 같이 같은 숫자가 적힌 카드가 있을 수 있다는 점에 유의해야 한다.

 

일반적인 문제처럼 ch 배열을 0과 1로 관리하면 같은 숫자가 나왔을 때 사용하지 않게 된다. 따라서 ch 배열에 각 숫자의 개수를 저장해두고 사용할 때마다 1씩 빼주었다. 그리고 dfs를 돌고 나오면 다시 더해준다. 따라서 조건도 ch[다음 숫자]가 0이 아닐 때이다.

 

그리고 k개를 선택하면 cnt를 1 증가시킨다. 이때 이미 만들어진 숫자의 경우 다시 cnt를 증가시키면 안되므로 nums 배열에 해당 값이 없을 때만 증가시킨다.

 

처음에는 ch 배열처럼 만들어진 해당 숫자를 인덱스로 해 만든 경우 0으로 아닌 경우 1로 관리하려고 했지만 배열 크기 때문에 메모리 초과가 났다. 그래서 만들어진 숫자를 push하고 Includes로 확인하는 방식으로 변경하여 해결하였다.