DFS - 최대점수 구하기

최대점수 구하기(DFS)

이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다.

각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩 니다.

제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)

 

▣ 입력설명

첫 번째 줄에 문제의 개수N(1<=N<=20)과 제한 시간 M(10<=M<=300)이 주어집니다.

두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다.

 

▣ 출력설명

첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력합니다.

 

▣ 입력예제 1

5 20

10 5

25 12

15 8

6 3

7 4

 

▣ 출력예제 1

41

---

해석

문제를 풀 때 걸리는 시간을 기준으로 부분집합을 구한 후, 요소의 합이 제한시간을 넘어가는지 확인한다.

제한 시간을 넘어가지 않는다면 문제를 풀 때 걸리는 시간에 매핑되는 점수를 구한 다음 점수의 최댓값을 리턴하면 된다.

let [a, ...table] = require('fs').readFileSync('input.txt').toString().trim().split('\n');
let [n, m] = a.split(' ').map(Number);
table = table.map((t) => t.split(' ').map(Number));
let map = new Map();
let ret = Number.MIN_SAFE_INTEGER;

function solve(idx, b) {
  let sum = b.reduce((acc, cur) => acc + cur, 0);
  if (sum > m) return;
  if (idx === n) {
    let totalScore = b.map((t) => map.get(t)).reduce((acc, cur) => acc + cur, 0);
    ret = Math.max(ret, totalScore);
    return;
  } else {
    b.push(table[idx][1]);
    solve(idx + 1, b);
    b.pop();
    solve(idx + 1, b);
  }
}

function solution() {
  table.forEach(([score, time]) => map.set(time, score));
  solve(0, []);
  return ret;
}

console.log(solution());

 

다른 풀이

let [a, ...table] = require('fs').readFileSync('input.txt').toString().trim().split('\n');
let [n, m] = a.split(' ').map(Number);
table = table.map((t) => t.split(' ').map(Number));
let ret = Number.MIN_SAFE_INTEGER;

function solve(idx, sum, time) {
  if (time > m) return;
  if (idx === n) {
    ret = Math.max(ret, sum);
    return;
  } else {
    solve(idx + 1, sum + table[idx][0], time + table[idx][1]);
    solve(idx + 1, sum, time);
  }
}

function solution() {
  solve(0, 0, 0);
  return ret;
}

console.log(solution());

해시맵을 사용하지 않고 solve 함수에 인자를 추가했다.

하나는 점수를 더하는 sum, 하나는 시간을 더하는 time이다.

시간이 제한시간을 넘어가는 경우에는 함수를 종료하고, 점수의 최댓값을 sum을 이용해서 구한다. 이전 코드보다 깔끔하다.

항상 재귀함수의 인자를 2개로 맞출 필요가 전혀 없다. 유연하게 활용하면 된다.