[백준] 블랙잭

문제 정리

N개의 숫자가 주어지고 그 중에서 3개를 선택해서 주어지는 모두 더한 값이 M보다 작거나 같은 값 중에서 가장 큰 값을 구하세요.

 

나의 생각

주어지는 N개의 숫자중에서 서로 다른 3개의 숫자를 선택하는 조합이라고 생각하였습니다. N개에서 3개를 선택하는 모든 경우를 구하기 위해서 DFS 알고리즘을 사용하였습니다.

 

지금까지는 DFS 알고리즘을 사용할때 배열에서 한번 선택한 값을 제거하기 위해서 filter를 사용하였습니다. 다른 사람의 풀이를 보았을 때 속도가 10배 이상 차이가 나는 것을 확인 하여 visited 배열을 사용하게 되었습니다.

이는 깊이 우선탐색 방법인 DFS의 특성 때문에사용 가능한 방법으로, 이번에 선택한 인덱스의 아이템은 깊이의 마지막에 도달하기 전까지 다시 재사용할일이 없기 때문입니다.

 

visited 사용 전

const fs = require('fs');

let [[N, M], input] = fs
  .readFileSync('example.txt')
  .toString()
  .trim()
  .split('\n')
  .map((v) => v.split(' '));

[N, M] = [N, M].map(Number);
input = input.map(Number);

let max = 0;

function dfs(input, sum) {
  if (sum > M) {
    return;
  }

  if (input.length === N - 3) {
    max = Math.max(max, sum);
    return;
  }

  for (let i = 0; i < input.length; i += 1) {
    dfs(input.filter((_, index) => index !== i), sum + input[i]);
  }
}

dfs(input, 0);

console.log(max);

visited 사용 후

const fs = require('fs');

let [[N, M], input] = fs
  .readFileSync('example.txt')
  .toString()
  .trim()
  .split('\n')
  .map((v) => v.split(' '));

[N, M] = [N, M].map(Number);
input = input.map(Number);

let max = 0;

function dfs(visited, sum, depth) {
  if (sum > M) {
    return;
  }

  if (depth === 3) {
    max = Math.max(max, sum);
    return;
  }

  for (let i = depth; i < N; i += 1) {
    if (!visited[i]) {
      visited[i] = true;
      dfs(visited, sum + input[i], depth + 1);
      visited[i] = false;
    }
  }
}

dfs([], 0, 0);

console.log(max);

	메모리	시간
visited 사용	10108 KB	192 ms
filter 사용	14084 KB	2804 ms