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

---

 

백준 - 단계별로 풀어보기 [2798] 

https://www.acmicpc.net/problem/2798

문제

 

 

카드의 개수 N과 타겟 값인 M을 첫 줄에 입력 받고,

둘째 줄에는 카드에 쓰여 있는 수가 입력될 때, 합이 M을 넘지 않도록 하는 카드 세장을 구해 이 카드들의 합을 출력하는 문제이다.

 

풀이

 

삼중 For문을 통해 카드 세장을 더한 값과 M과의 차이를 구하고, 

가장 차이가 작은 값의 합을 출력해주면 풀이가 가능한 문제이다.

 

분류가 Brute Force인 만큼, 모든 카드의 조합을 고려한 후 합이 가장 작은 값을 찾아주면 된다.

이 때, 동일한 값을 가지는 카드가 존재할 수 있으므로 DFS를 활용한 조합으로 접근하면 오답이 될 수 있다.

 

코드

 

#include <iostream>
#define MAX 100
using namespace std;

int main() {
    int num, target,goal,sum = 0;
    int min = 9999999;
    int arr[MAX] = {0, };
    cin >> num >> target;
    for(int i = 0; i < num; i++)
        cin >> arr[i];

    for(int i = 0; i < num-2; i++)
        for(int j = i+1; j < num-1; j++)
            for(int k = j+1; k < num; k++)
            {
                sum = arr[i]+arr[j]+arr[k];
                if(target - sum < min && target - sum >= 0) {
                    min = target - sum;
                    goal = sum;
                }
            }
    cout << goal;
}

 

평가

 

삼중 For문이 워낙 안좋은 풀이 방법이라는 생각 때문에, 다른 방식으로 풀어보려고 하였으나 본 문제에서는 삼중 For문으로 작성했을때 가장 간결한 코드를 가지는 듯하다.