📘[백준-2798] 블랙잭(C)

블랙잭 문제

블랙잭 문제는 주어진 카드와 최대 숫자를 입력받고, 주어진 카드 중 3개를 선택해 그 합이 최대 숫자에 가장 근접하게 맞추는 문제이다.

[입력]

5 21
5 6 7 8 9

[출력]

21

브루트 포스는 모든 경우의 수를 전부 탐색한다.
나는 이 문제를 풀기 위해 3번의 for문을 거쳤다.

먼저 조건에 맞게 값들을 입력 받을 것이다.
그 다음 첫 번쨰 for문의 조건식은 아래와 같다.

for(int i=0; i<N-2; i++)

(주어진 카드의 개수 - 2) 인 N-2만큼 반복하는 이유는 i = 0, 1, 2, ... , N-3 까지 반복할 것이고, 그래야 뒤에 카드를 2개 더 뽑아 총 3개의 카드를 뽑을 수 있기 때문이다.

그 다음 for문의 조건식은 아래와 같다.

for(int j=i+1; j<N-1; j++)

앞선 for문 안에서 동작하며, j=i+1인 이유는 이미 앞서 1장의 카드를 선택했기 때문이다.
위와 같은 이유로 반복하는 구간의 종점은 N-1이다.

마지막 for문의 조건식은 아래와 같다.

for(int k=j+1; k<N; k++) 

마찬가지로 j에서 한 장을 뽑았으니 k=j+1부터 시작하고, 종점은 끝까지 반복해야 하므로 N이 된다.

최종적인 코드는 아래와 같다.

[코드]

// N(3<=N<=100), M(10<=M<=300000)
// 최대한 M과 가깝게 만든다

#include <stdio.h>

int blackjack(int N, int M, int *cards);

int main() {
    
    // N(뽑는 카드의 수)
    // M(맞춰야 하는 카드의 숫자 합)
    int N, M;
    scanf("%d %d", &N, &M);

    if(3>N || N>100 || 10>M || M>300000) {
        printf("범위 오류");
        return 0;
    }

    // 책상에 놓여진 카드
    int cards[N];
    for(int i=0; i<N; i++) {
        scanf("%d", &cards[i]);
    }

    blackjack(N, M, cards);

    return 0;
}

int blackjack(int N, int M, int *cards){
    int result = 0;
    int sum = 0;
    int check = 0;
    
    for(int i=0; i<N-2; i++) {
        for(int j=i+1; j<N-1; j++) {
            for(int k=j+1; k<N; k++) {
                sum = cards[i] + cards[j] + cards[k];
                if(sum > result && sum <= M)
                    result = sum;
            }
        }
    }
    printf("%d", result);

    return result;
}