문제

곧 졸업을 앞둔 민호는 대학교 생활 동안 구매만 해놓고 한 번도 펴보지 않은 전공책에 먼지가 쌓여 있는 것을 보고는, 이 책들을 어떻게 처리해야 할지 고민 중이다. 열심히 고민한 끝에 민호는 결국 전공책을 모두 버리기로 마음먹었다. 하지만 그냥 버리기엔 심심한 민호는 전공책 제목에 있는 글자들을 오려서 단어 만들기 놀이를 하려고 한다. 단어 만들기 놀이는 아래 예시와 같다.

1번 책 : COMPUTERARCHITECTURE (35,000원)
2번 책 : ALGORITHM (47,000원)
3번 책 : NETWORK (43,000원)
4번 책 : OPERATINGSYSTEM (40,000원)

만약 민호가 만들고 싶은 단어가 ALMIGHTY라고 하면, 위 4개의 책 중, 1번 책에서 A를, 2번 책에서 L, M, I, G, H, T를, 4번 책에서 Y를 오려내어 원하는 단어를 만들 수 있다. 이때 드는 비용은 1번, 2번, 4번 책 가격의 합인 122,000원이다.

만약 ANT라는 단어를 만들고 싶다고 하면, 2번 책에서 A를, 3번 책에서 N, T를 오려내어 원하는 단어를 만들 수 있다. 이때 드는 비용은 2번과 3번 책 가격을 합하여 90,000원이다. 그런데, ANT라는 단어에서 A를 2번 책에서 오려내지 않고, 4번 책에 있는 A를 오려낼 수도 있다. 만약 4번 책에서 A를 오려냈을 때 드는 비용은 3번과 4번 책 가격을 합하여 83,000원으로 2번과 3번 책을 고른 비용보다 작다. 하지만, 4번 책에는 ANT가 모두 포함되어 있으므로, 4번 책만 선택했을 때 드는 비용이 40,000원이다. 이는 ANT라는 단어를 만들기 위해서 가장 적은 비용이다.

민호는 여러 개의 전공책들을 나열해 놓고는, 심각한 고민 끝에 전공책 제목에 있는 글자를 오려내어 자신이 원하는 단어를 만들기 위해서는 여러 가지 경우가 있다는 것을 깨달았다. 매우 심심했던 민호는 가장 적은 비용으로 자신이 원하는 단어를 만들려면 어떤 전공책들을 선택해야 하는지 궁금했다. 하지만 일일이 가능한 조합을 만들어 보는 것은 매우 시간 낭비라고 생각한 민호는 컴퓨터공학과답게 프로그램을 만들려고 한다.

민호를 도와 각 전공책의 가격과 제목이 주어졌을 때, 가장 적은 비용으로 민호가 원하는 단어를 만들기 위해서 어떤 전공책을 선택해야 하는지 알아보자.

입력

첫 번째 줄에는 민호가 만들고자 하는 단어를 의미하는 문자열 T (1 ≤ |T| ≤ 10)가 주어진다. T는 항상 대문자이며, |T|는 문자열 T의 길이를 의미한다.

두 번째 줄에는 민호가 가진 전공책의 개수를 의미하는 정수 N (1 ≤ N ≤ 16)이 주어진다.

다음 N개의 각 줄에는 전공책 가격을 의미하는 정수 Ci (10,000 ≤ Ci ≤ 100,000)와 제목을 의미하는 문자열 Wi (1 ≤ |Wi| ≤ 50)가 주어진다. Wi는 항상 대문자이다.

출력

민호가 원하는 단어 T를 만들기 위해서 선택해야 하는 전공책의 가장 적은 가격의 합을 출력한다. 만약 단어를 만들 수 없다면 -1을 출력한다.

예제 입력

ANT
4
35000 COMPUTERARCHITECTURE
47000 ALGORITHM
43000 NETWORK
40000 OPERATINGSYSTEM

예제 출력

40000

내가 했던 풀이 방법

1. min값을 Infinity로 설정한다.
2. DFS를 수행한다. DFS는 str(찾아야 하는 단어), price(필요한 가격), start(검사를 시작하는 책의 index)를 필요로 한다. str의 길이가 0이 되면 min값을 설정해주고 return 한다. start부터 N-1까지 book 배열을 순회한다. 이때, 현재까지의 str을 newStr에 저장해주고, 현재 책 제목을 단어 하나씩 검사하면서 찾아야 하는 단어가 포함된 경우, 해당 단어를 newStr에서 제거해준다. for문이 끝나면 newStr에는 찾지못한 알파벳만 남게 된다. 다음 DFS로 찾지못한 단어들을 전달하고, price에 현재까지의 책 값(이번에 사용한 가격 포함)을 전달해준다.
3. DFS를 수행하게 되면 min에는 가장 최소의 책 값이 저장되어 있다. 만약 이 값이 Infinity라면 -1을 출력하고, 그게 아니라면 min을 출력해준다.

코드

const fs = require('fs');
let [str, N, ...book] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

str = str.trim().split('').sort();
N = Number(N);

for (let i = 0; i < N; i++) {
  book[i] = book[i].trim().split(' ');
}

let min = Infinity;
function DFS(str, price, start) {
  if (str.length === 0) {
    if (min > price) {
      min = price;
    }
    return;
  }

  for (let i = start; i < N; i++) {
    let newStr = [...str];
    for (let word of book[i][1]) {
      const index = newStr.indexOf(word);
      if (index !== -1) {
        newStr.splice(index, 1).join('');
      }
    }

    DFS(newStr, price + Number(book[i][0]), i + 1);
  }
}

DFS([...str], 0, 0);
if (min === Infinity) console.log(-1);
else console.log(min);

회고

지금까지 풀었던 DFS 문제 중에는 어려웠던 것 같다. 재귀 횟수는 적지만, 고려해주어야 하는 것들도 좀 있고, 문제를 딱 보고 바로 풀이 방법이 생각나지는 않았다. 처음에는 정렬해준 다음 한 권의 책으로 문자열을 다 찾는 경우 / 가장 저렴한 책에서 문자들을 찾는 경우를 찾아서 더 작은 값을 구하면 되겠다고 생각했는데 생각해보니 그렇게 되면 여러 책으로 분산될 수 있다는 것을 고려하지 못했다. 조금만 더 생각했으면 100% 혼자서 풀 수도 있었을 것 같기도 하면서... 혼자했으면 못 풀었을 것 같기도 하면서... 튼 생각!보다는 어려웠던 문제