[JS][백준]2798_블랙잭

문제 번호

2798번: 블랙잭

 

 

알고리즘 분류

 브루트포스

 

문제 풀이

주어진 모든 경우를 다 탐색해보면된다.

문제를 처음 풀었을때는 C++를 이용하여 3중 for문을 사용하였었다.

그러나 문제를 풀어볼수록 for문을 여러번 사용하는 방법은 금방 한계를 맞이했던 기억이 있어서 재귀를 사용하여 문제를 풀어보기로했다.

 

cards 배열에 문제에서 주어진 N장의 카드들을 입력받고, picked란 배열을 사용하여서 해당 카드들이 선택되었는지 아닌지 알 수 있도록 하였다.

const fs = require('fs');
const input = fs.readFileSync('2798_블랙잭/input.txt').toString().split('\n');

const NM = input.shift().split(' ').map(num => Number(num));
const N = NM.shift();
const M = NM.shift();
const cards = input.shift().split(' ').map(num => Number(num));
let picked = new Array(N);
picked.fill(false, 0, N);

shift와 split, 그리고 map을 이런식으로 사용할 수 있다는건 다른 블로그를 통하여 알았다.

 

 

M의 최대값은 300,000이므로 가장 가까운 합은 300,000 이하 일 것이다. 따라서 3장의 합과 M과의 차이를 나타내는 변수 min, 3장의 합을 나타내는 변수 sum 그리고 정답을 나타낼 변수 answer를 사용하였다.

let min = 300000;
let sum = 0;
let answer = 0;

 

 재귀를 통하여 3장의 카드를 모두 뽑을때까지 solution 함수를 반복하였다.

3장의 카드를 모두 선택하였다면 그때의 합이 M에 가장 가까운 값인지 확인하는 과정을 거쳤다.

function solution(last, start) {
  if (last === 0) {
    if (sum <= M && M - sum < min) {
      min = M - sum;      
      answer = sum;
      return sum;
    }
    return;
  }

  for (let i = start; i < cards.length; i++) {
    if (!picked[i]) {
      picked[i] = true;
      sum += cards[i];
      solution(last - 1, i);
      picked[i] = false;
      sum -= cards[i];
    }
  }
}

 

 이처럼 재귀함수를 사용하여 브루트포스 알고리즘을 해결할때

 - if(대상이 선택된 적이없다.)

 - 대상을 선택했다고 표시한다.

 - 문제에 따라 변수들의 값을 바꾼다.

 - 재귀 호출한다.

 - 대상을 선택한적 없다고 되돌린다.

 - 문제에 따라 바꾸었던 변수들의 값을 되돌린다.

의 형태를 띄고있다. (내가 푼 문제들은 그랬다.)

 

전체코드

const fs = require('fs');
const input = fs.readFileSync('2798_블랙잭/input.txt').toString().split('\n');

const NM = input.shift().split(' ').map(num => Number(num));
const N = NM.shift();
const M = NM.shift();
const cards = input.shift().split(' ').map(num => Number(num));
let picked = new Array(N);
picked.fill(false, 0, N);

let min = 300000;
let sum = 0;
let answer = 0;


solution(3, 0);
console.log(answer);

function solution(last, start) {
  if (last === 0) {
    if (sum <= M && M - sum < min) {
      min = M - sum;      
      answer = sum;
      return sum;
    }
    return;
  }

  for (let i = start; i < cards.length; i++) {
    if (!picked[i]) {
      picked[i] = true;
      sum += cards[i];
      solution(last - 1, i);
      picked[i] = false;
      sum -= cards[i];
    }
  }
}

특이사항