[BOJ / 백준] 2798번 블랙잭 C++ 풀이

안녕하세요! 다들 늦었지만 새해 복 많이 받으세요!
작년에 토이 프로젝트를 조금 하면서 코딩 실력이 부족함을 많이 느껴가지고 올해는 알고리즘 공부도 열심히 하려고 합니다. 그리고 푼 문제를 오답노트처럼 블로그에 올리려고 합니다.

---

블랙잭 2798번은 브루트포스 문제입니다.
https://www.acmicpc.net/problem/2798

문제의 기본 알고리즘을 아래와 같이 N(숫자의 수)과 M이 주어지고 세 수중에서 모든 수의 합 중에서 M보다 작으면서 M과 가장 가까운 수를 구하는 문제입니다.

위 알고리즘을 코드로 구현하면 아래와 같습니다.

이 문제의 포인트는 삼중 반복문으로 인덱스(i,j,k)를 정하고 다 더해서 각 경우의 합을 구하는 것입니다.
두 번째로는 타겟변수 M과의 차이를 비교할 때 dfr(difference) 변수 초깃값을 크게 잡아가지고 처음 if(M-sum~)에서 자동으로 dfr에 첫 번째 경우의 차이 값을 할당하는 것입니다.

아래는 초기 코드입니다. 저는 반복문을 돌릴 때 index out of range가 날까봐 첫 번째 if 문을에서 인덱스가 뒤에서 3개의 수만 남았을 때 break 하려고 했는데 조금 고민하다 다른 블로그의 코드를 참고해서 아래 코드를 최적화해봤습니다.

#include <iostream>
using namespace std;
 
unsigned int N, M, sum, fix,tmp,targetSum;
unsigned int dfr = 100;
unsigned int arr[10000];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();
 
    // 숫자 입력 받기
    cin >> N >> M;
    
    // 반복문으로 N만큼의 수 입력 받기
    for (int i = 0; i < N; i++)
    {
        cin >> arr[i];
    }
 
    // 전체 합의 경우 구하는 반복문
    for (int i = 0; i < sizeof(arr); i++)
    {
        if (i == sizeof(arr) - 3)
        {
            break;
        }
 
        for (int j = i+1; j < sizeof(arr);j++)
        {
            for (int k = j+1; k < sizeof(arr); k++)
            {
                sum = fix + arr[k];
 
                // M이하이고 M과 가장 가까운 수 구하기 
                tmp = M - sum;
                if ((tmp < dfr) && (M <= sum))
                {
                    dfr = tmp;
                    targetSum = sum;
                }
            }
        }
 
    }
    
    cout << targetSum;
    return 0;
}
 

위에서 언급했던 배열의 범위는 굳이 조건문을 걸지 않고 첫 번째 반복문에서 N-2로 수정하고 메모리를 차지하는 tmp, fix와 같은 반복되는 변수를 수정하였습니다.

#include <iostream>
using namespace std;
 
unsigned int N, M, sum,targetSum;
unsigned int dfr = 9999999;
unsigned int arr[10000];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();
 
    // 숫자 입력 받기
    cin >> N >> M;
    
    // 반복문으로 N만큼의 수 입력 받기
    for (int i = 0; i < N; i++)
    {
        cin >> arr[i];
    }
 
    // 전체 합의 경우 구하는 반복문
    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 = arr[i] + arr[j] + arr[k];
 
                // M이하이고 M과 가장 가까운 수 구하기 
                if ((M - sum < dfr) && (M >= sum))
                {
                    dfr = M - sum; // M과 각 경우의 차이를 저장
                    targetSum = sum;
                }
            }
        }
 
    }
    
    cout << targetSum;
    return 0;
}
 
 

감사합니다!