블랙잭

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

2798번: 블랙잭

접근 방법

블랙잭 문제는 대표적인 완전 탐색 알고리즘이다. 

• M(카드의 합)을 넘지 않으면서 M에 최대한 가까운 카드 3장

카드의 합보다 작은 수는 모두 무시하고 카드 3장을 찾을것이기 때문에 3중 for문을 사용하여 각 수의 합을 얻는다.

코드

function solution(card, sum, arr) {
  let answer = 0;
  for (let i = 0; i < card; i++) {
    for (let j = i + 1; j < card; j++) {
      for (let k = j + 1; k < card; k++) {
        let tmp = arr[i] + arr[j] + arr[k];
        if (tmp > answer && tmp <= sum) {
          answer = tmp;
        }
      }
    }
  }
  return answer;
}

solution(10, 500, [93, 181, 245, 214, 315, 36, 185, 138, 216, 295]);

3중 for문을 통해 각각의 수에 접근을 하면 된다. 

이때 시간 복잡도는 O(n^3)이 나오게 된다. 

이 문제는 완전탐색 알고리즘의 매우 기초적인 문제이다.