추석맞이 코딩 문제 챌린지 LV.3 블랙잭

 

[추석맞이 코딩챌린지③] 블랙잭

 

문제

카지노에서 자주 플레이되는 블랙잭의 규칙은 카드의 합이 21이 넘지 않는 한도 내에서, 카드의 합을 가장 크게 만드는 게임이다.

이와 유사하게, 코드메이트 버전의 블랙잭은 N개의 카드 중 세장의 카드를 뽑아 X를 넘지 않으면서 X와 가장 가까운 수의 카드 조합을 골라내는 규칙으로 진행된다.

 

첫째 줄에는 카드의 개수 N과 목표 값 X가 주어지며,

두 번째 줄에는 카드에 쓰여있는 수가 입력으로 주어질 때,

X에 가장 가까우면서 X를 넘지 않는 카드 세장의 합을 구해서 출력하세요.

 

입출력 예시

예제 입력 1

5 21
1 2 3 4 5

예제 출력 1

12

 

예제 입력 2

8 100
16 85 30 14 95 63 52 87

예제 출력 2

98

 

---

힌트

N개의 카드 중 세장의 카드를 뽑아 X를 넘지 않으면서 X와 가장 가까운 수를 구하면 되는 문제이다.

3장의 카드를 선택할 수 있는 경우의 수를 3중 반복문으로 구현해보자.

 

---

정답 코드

- C언어

#include <stdio.h>
#include <stdlib.h>     // malloc, free를 사용하기 위해 포함

int main(){
    int N, X, *cards, result = 0;
    
    scanf("%d %d", &N, &X);

    // 블랙잭
    // N개의 카드 중 3개의 카드를 뽑아 더했을 때
    // X를 넘지 않으면서 X에 최대한 가까운 합을 구하여라

    // N이 상수가 아닌 변수이기 때문에 동적 할당을 통해
    // 입력받을 메모리 공간을 확보해준다.
    cards = malloc(sizeof(int) * N);        

    for(int i = 0; i < N; i ++){        // N개의 카드를 입력받는다
        scanf("%d", &cards[i]);
    }

    // 3중 반복문을 수행할 때
    // 겹치는 경우의 수나 카드를 중복해서 뽑는 경우가 없도록 한다.
    for(int i = 0; i < N; i ++){
        for(int j = i + 1; j < N; j ++){
            for(int k = j + 1; k < N; k ++){
                int total = cards[i] + cards[j] + cards[k];     // 뽑은 3개의 카드를 더한다
                int gap = X - total;            // X와의 차를 계산한다.

                // gap이 0보다 작으면 3개 카드의 합이 X를 넘어간다는 의미이므로
                // gap은 0보다 크거나 같아야한다.
                // gap이 X - result보다 작으면 X에 더 가깝다는 의미이므로
                // 결과를 갱신해준다.
                if(gap >= 0 && gap < X - result){
                    result = total;
                }
                
            }
        }
    }

    printf("%d", result);

    free(cards);        // 동적할당 후 반드시 해제해준다.

    return 0;
}

- Python

# 블랙잭
# N개의 카드 중 3개의 카드를 뽑아 더했을 때
# X를 넘지 않으면서 X에 최대한 가까운 합을 구하여라

N, X = map(int, input().split())                # N과 X를 입력받는다.
cards = list(map(int, input().split()))         # N개의 카드를 입력받는다
result = 0          # 결과를 저장할 변수

# 3중 반복문을 수행할 때
# 겹치는 경우의 수나 카드를 중복해서 뽑는 경우가 없도록 한다.
for i in range(N):
    for j in range(i + 1, N):       # j는 i + 1부터 시작한다.
        for k in range(j + 1, N):
            total = cards[i] + cards[j] + cards[k]      # 뽑은 3개의 카드를 더한다
            gap = X - total                             # X와의 차를 계산한다.

            # gap이 0보다 작으면 3개 카드의 합이 X를 넘어간다는 의미이므로
            # gap은 0보다 크거나 같아야한다.
            # gap이 X - result보다 작으면 X에 더 가깝다는 의미이므로
            # 결과를 갱신해준다.
            if gap >= 0 and gap < X - result:
                result = total

print(result)

 

---

풀이

N개의 카드 중 3개의 카드를 뽑는 경우의 수를 계산하기 위해 3중 반복문을 사용했다.

3개의 카드의 합을 구한 다음 문제의 요구 조건대로 합이 X가 넘지 않으면서 X에 더 가까운 합으로 갱신시켜주면 된다.

 

---

심화

브루트포스 알고리즘

이번 문제에서 3중 반복문을 통해 3개의 카드를 뽑아 나올 수 있는 모든 경우의 수를 탐색하였다. 이렇게 모든 경우를 다 탐색하여 결과를 도출해내는 알고리즘을 브루트포스 알고리즘 또는 완전 탐색이라고 부른다.