[코테/JAVA] 브루트 포스 : 블랙잭

2022.06.15

97번째 글.

코테 문제풀이 20주차 1번 문제

 

 

문제

  ① 브루트 포스 : 블랙잭

  ② 문제설명

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다. 이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다. N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

 

  ③ 링크

2798번: 블랙잭

 

 

접근방법

  생각해낸 방법은 1가지

  ① DFS

 

 

풀이

  ① 접근방법 : ①

  ② 풀이

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

package codingTest;   import java.util.Scanner;   public class T20220614v1 {          static int answer = 0;          public static void main(String[] args) {         /*          * Date: 2022-06-14          * Time: 23:36          */                  /**          * Input 입력          * 1. Scanner 클래스를 통해 Input을 직접 입력 받음          * 2. n장의 카드의 값들을 고정배열로 생성          */         Scanner sc = new Scanner(System.in);         int n = sc.nextInt();         int m = sc.nextInt();         int[] arr = new int[n];         for (int i = 0; i < n; i++) {             arr[i] = sc.nextInt();         }         sc.close();                  blackJack(arr, n, m, 0, 0);     }          /**      * 메소드명: 블랙잭      * Input      * arr        카드숫자고정배열      * n        카드의장수      * m        타겟값      * loop        DFS탐색횟수      * sum        카드의합        * 1. 탐색횟수(loop)는 카드의장수(n)를 넘을 수 없다.      * 2. 카드의합(sum)은 타겟값(m)을 넘을 수 없다.      * 3. DFS를 통해 모든 경우의 수를 탐색한다.      */     public static void blackJack(int[] arr, int n, int m, int loop, int sum) {                  if (loop == n) {             answer = answer < sum ? sum : answer;             return;         } else if (sum + arr[loop] > m) {             answer = answer < sum ? sum : answer;             return;         } else {             blackJack(arr, n, m, loop + 1, sum + arr[loop]);             blackJack(arr, n, m, loop + 1, sum - arr[loop]);         }     } }   Colored by Color Scripter

cs

 

 

결과

 

주의사항

  ① DFS보다는 백트래킹으로 풀어야 한다.

  ② DFS로도 정답은 찾을 수 있지만 시간초과가 발생한다.