백준 2798번 블랙잭

주어진 각 카드 숫자중에(arr[]에 있는) 3개를 선택해서 숫자가 안겹치게 알고리즘을 짜야겠다고 생각했다.
그렇게 해서 더한 각 숫자를 sum배열에 넣고 M보다 작거나 같고 이전에 받았던 수보다 큰 수 라면 result 에 넣으라고 알고리즘을 짰다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
    int N, M;
    int sum[1000] = { 0 };
    int arr[1000] = { 0 };
    int t = 1;
    int result = 0;
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) scanf("%d", &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[t] = arr[i] + arr[j] + arr[k];
                if (sum[t] > sum[t - 1] && sum[t] <= M) {
                    result = sum[t];
                    t++;
                }
            }
        }
    }
    printf("%d", result);
    
}

근데 sum 배열은 없어도 된다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int max(int a, int b) {
    if (a < b) {
        return b;
    }
    return a;
}

int main() {
    int N, M;
    int arr[1000] = { 0 };
    int sum;
    int result = 0;
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) {
        scanf("%d", &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];
                if (sum <= M) {
                    result = max(result, sum);
                }
            }
        }
    }
    printf("%d", result);

}

블랙잭 문제는 브루트포스 알고리즘의 대표적인 문제라고한다.
브루트포스 알고리즘이란 위 코드와 같이 모든 경우의 수를 비교하여 결과를 도출하는것이다.
한마디로 무식하게 전부다 비교해본다고 할 수있다.

브루트 포스의 장점

복잡한 알고리즘 없이 빠르게 구현할수있고, 쉽다.

브루트 포스의 단점

모든 경우의 수를 비교하여 결과를 도출하는 만큼 시간도 오래걸리고 메모리 효율도 비효율 적이다.

느낀점.

브루트 포스로만 풀려고 하는 습관을 좀 개선해야겠다.