[C언어] 백준 2798 : 블랙잭

내가 한 문제의 이해

n개의 카드 수 중, 나는 3장을 뽑을 것이다. 그 3장을 더한 값이 M과 제일 가까운 수를 출력한다.

• 먼저 브루트 포스가 뭔지 몰랐기 때문에 브루트 포스가 뭔지 검색을 했다.
  쉽게 말하면, 모든 경우의 수를 가지고 100%의 '정답'을 출력하는 것이다.

• 모든 경우의 수를 알기 위해 3장을 뽑아 합을 다 배열에 입력했다.
  예를 들어 5장의 카드를 펼친다면, 5C3으로 10가지의 경우의 수가 있다. arr[0] ~ arr[9]까지 각각 합을 넣어주었다.
  여기까지 우리는 3장을 뽑고, 경우의 수를 다 알고있다.

• 그 경우의 수가 M과 제일 가까운지 확인을 해야한다. 단, M을 넘으면 안된다.
  예를 들어 M = 21인데, 우리가 가진 3장의 카드가 22, 23... 이면 안된다. 21, 20, 19...이런것만 체크해야 한다.
  M - arr[0] ~ arr[9]까지 다 돌렸고, 그 값이 0이거나 양수일 경우(21, 20, 19...)만 고려를 해주며, 그 경우의 수들 중 제일 큰 값을 찾는다.

• 그 제일 큰 값에 * -1을 해준 후 M을 더하며 출력.
  예를 들어 M = 21이고, 가장 가까운 수가 18이면, 차이는 3인데 여기서 21을 더해버리면 24가 된다. 그러므로 3에 -1을 곱하고 M을 더해 18을 출력한다.

내가 푼 코드

#include <stdio.h>

int main()
{
    int i, j, k, M;
    int n, min, count = 0;
    scanf("%d", &n);
    scanf("%d", &M);
    int nb[n];
    int arr[n * (n - 1) * (n - 2) / 6]; // nC3 계산.
    i = 0;
    while (i < n)
    {
        scanf("%d", &nb[i]); // 깔리는 카드 수에 맞춰 각각 숫자 입력
        i++;
    }
    i = 0;
    while (i < n - 2) // i는 마지막보다 -2만큼 돌아야 한다. 3개를 뽑기 때문.
    {
        j = i + 1; // j는 항상 i보다 1 크게 시작한다.
        while (j < n - 1) // j는 마지막보다 -1
        {
            k = j + 1;
            while (k < n)
            {
                arr[count] = nb[i] + nb[j] + nb[k];
                count++;
                k++;
            }
            j++;
        }
        i++;
    }
    i = 0;
    min = arr[0];
    while (i < count)
    {
        arr[i] = M - arr[i]; // M과 가까운 수 체크
        if (arr[i] >= 0) // M보다 크면 고려 안하기에 M보다 작거나 같은 수 고려.
        {
            if (arr[i] < min)
            {
                min = arr[i];
            }
        }
        i++;
    }
    printf("%d", min * -1 + M);
}

다른 사람 풀이

#include <stdio.h>
int main(void)
{
    int n, m;
    int sum, max = 0;
    int i, j, k;
    int arr[100] = {0};
    int count = 0;
    scanf("%d %d", &n, &m);
    sum = m;
    for (i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    for (i = 0; i < n - 2; i++)
    {
        for (j = i + 1; j < n - 1; j++)
        {
            for (k = j + 1; k < n; k++)
            {
                sum = arr[i] + arr[j] + arr[k];
                if (sum <= m && max < sum)
                    max = sum;
            }
        }
    }
    printf("%d", max);
    return 0;
}

차이점

• 나는 모든 경우의 수를 계산하기 위해 arr[nC3]을 했는데 다른 사람들은 sum에다가 입력받고, 그 sum 값으로 바로 M에 근접한 값을 저장해버린다.
  따라서 메모리적으로 나는 손해보았다. 카드가 깔리는 수가 많아지면 손해가 커진다..

• 그리고 가만히 생각해보니 굳이 비교하려고 M - arr[i]를 할 필요도 없었겠구나 싶다. 쓰더라도 M - arr[i]가 아닌 arr[i] - M을 했으면 프린트할때 -1을 안곱해줘도 되겠고..

• 그래도 논리는 같다는 점에서 만족한다. 배울게 많다