백준 2798 - 블랙잭

 

 

2798번: 블랙잭

서론

해당 문제는 브루트 포스 알고리즘(완전 탐색)을 이용하여 풀 수 있는 문제입니다.

백준 단계별 학습에서 나오는 가장 기본적인 브루트 포스 알고리즘 문제 중 하나입니다.

 

문제 파악

우선 해당 문제에 대한 내용을 정리해보도록 합시다. 

 

• 카드의 개수 N개를 입력받는다.
• 원하는 카드의 합 M을 입력받는다.
• N개만큼의 카드의 번호를 각각 입력받는다.
• 카드(N)는 최소 3개 최대 100개만 존재할 수 있다.
• 각각의 카드 N은 0~100,000의 양수이다.
• 카드(N)를 3개 조합해서 카드의 합(M)과 가장 근사한 값을 구한다.
• 단, 3개의 카드를 조합하는 과정에서 카드의 합을 넘는 값은 고려하지 않는다.

구현 준비

구현을 하기 위해서 브루트 포스 알고리즘을 적용한다고 말했습니다.

2가지 방법으로 구현할 수 있습니다.

• 재귀적 표현
• 반복적 표현

각각의 방법으로 구현을 해보도록 합시다.

 

구현 1 - 재귀적 표현

 

재귀적인 방법으로 구현을 하면 소스코드가 간결해지는 특성을 가지고 있습니다. 

#include <stdio.h>


//전역 변수
int N,M;  // N : 카드의 개수 M : 목표 값
int cards[100]; // N개의 카드를 저장할 배열
int result; // M에 가장 근접한 결과를 저장할 변수

//재귀함수를 통한 해결

//매개변수
//  idx : 탐색할 인덱스
//  cnt : 합한 카드를 카운팅 할 변수
//  sum : 합한 값을 저장할 변수
void solve(int idx,int cnt,int sum){
    
    // 두가지 종료조건이 필요합니다.
    // 1.참조 범위가 카드의 개수 N을 초과할 때
    // 2.카운팅수가 3개 즉 3개의 합이 완성되 었을 때
    
    
    
    // 1번 종료조건
    if(idx > N){
        return;
    }
    // 2번 종료조건
    if(cnt == 3){

        //기존에 기억한 결과값과 현재 더한 값을 비교
        if((M-sum) >= 0 && (M-sum) < (M-result)) result = sum;
        else result = result;
        
        //printf("계산 값 : %d\n",sum);
        return;
    }

    
    //순차적으로 인덱스 한번 증가,카운팅한번 증가, 카드의 값 더하며 함수 호출
    solve(idx+1,cnt+1,sum+cards[idx]);
    
    //인덱스 값만 증가하며 다른 경우의 수를 완전 탐색하기 위한 함수 호출
    solve(idx+1,cnt,sum);
    return;
}


//프로그램 구동 부
int main() {

    //N,M을 입력 받는다.
    scanf("%d",&N);
    scanf("%d",&M);
    
    //N개의 카드의 번호를 입력 받는다.
    for(int i = 0 ; i < N ; i++){
        scanf("%d",&cards[i]);
    }
    
    //해결을 위해 재귀함수를 호출한다.
    solve(0,0,0);
    
    //결과를 출력한다.
    printf("%d\n",result);
    return 0;
}

구현 2 - 반복적 표현

반복적 표현을 사용하여 구현해 봤습니다. 사실 해당 문제의 경우 반복적 표현이 간결할 수 있습니다.

#include <stdio.h>


//전역 변수
int N,M;  // N : 카드의 개수 M : 목표 값
int cards[100]; // N개의 카드를 저장할 배열
int result; // M에 가장 근접한 결과를 저장할 변수

//프로그램 구동 부
int main() {

    //N,M을 입력 받는다.
    scanf("%d",&N);
    scanf("%d",&M);
    
    //N개의 카드의 번호를 입력 받는다.
    for(int i = 0 ; i < N ; i++){
        scanf("%d",&cards[i]);
    }
    
    //반복적 표현으로 구현
    for(int i = 0 ; i < N ; i++){
        for(int j = i+1 ; j < N ; j++){
            for(int k = j+1 ; k < N ; k++){
                int sum = cards[i]+cards[j]+cards[k];
                    //기존에 기억한 결과값과 현재 더한 값을 비교
                    if((M-sum) >= 0 && (M-sum) < (M-result)) result = sum;
                    else result = result;
            }
        }
    }
    
    //solve(0,0,0);
    
    //결과를 출력한다.
    printf("%d\n",result);
    return 0;
}