[JAVA] 2798번 블랙잭 🤎2 : 나의 첫 무서운 브루트포스 알고리즘 풀이

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

 

입력

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

 

 

나의 생각

문제 이해 자체는 그렇게 어렵지 않다. 그냥 N번만큼 숫자를 받고 3개씩 더해서 그 합이 M을 넘지 않으면서 M과 최대한 가깝게 하는 합을 구하면 되는 것이다.

와 근데 딱 든 생각은 아니 경우의 수가 너무 많은데??? 였다.

그래서 최대한 간결하게 풀 수 있는 방법이 없을까... 하다가 백준문제를 보면 아래 알고리즘 분류가 적혀있는데 거기에 브루트포스 알고리즘 이라고 적혀있었다.

원래는 보면 안되지만 아직 나는 알고리즘 이론을 배운 상태가 아니라 뭔지도 모르고 일단은 풀어나갔다....

그래서 한 풀이는 

 

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }
        int max = Integer.MIN_VALUE;

        for (int i = 0; i < N; i++) {
            for (int j = i+1; j < N; j++) {
                for (int k = j+1; k < N; k++) {
                int temp = arr[i] + arr[j] + arr[k];
                if(temp>max && M >= temp) max = temp;
                }
            }
        }
        System.out.println(max);
    }
}

무식하게 그냥 삼중포문으로 풀어나갔다. 근데 아직은 크게 시간초과에 대해서 신경을 안쓰고 풀이를 하느라 일단 제출을 했는데 맞긴 맞았다.  그러고 나서 좀 더 알아보니
이 문제같은 경우는 제한시간 1초.   

보통 알고리즘 문제 풀이에서 보통 1초 동안 처리할 수 있는 연산 횟수는 10^8 정도로 본다고 한다....!!

다행히 100*100*100 , 즉 10^6이라 시간제한은 안걸린 것 같다.

그러고 나서 브루트포스 알고리즘에 대해서 검색을 했더니 이름만 무서웠지 별거 아닌놈이었다!

 

브루트포스(Brute Force) 알고리즘은 가능한 모든 경우의 수를 일일이 탐색하여 문제의 해답을 찾는 방법이다. 휴 이 정의를 보니 접근 자체는 다행히 맞았구나 라는 생각이 들었다.  상황에 따라서는 이분 탐색, 다이나믹 프로그래밍, 백트래킹 등의 방법으로 최적화할 필요가 있다고 하는데, 난 아직 저것들을 하나도 몰라서 ㅎㅎ 얼른 배워보고 적용해보고 싶다!

 

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();  // 카드의 개수
        int m = sc.nextInt();  // 목표 합
        int[] cards = new int[n];

        // 카드 값 입력
        for (int i = 0; i < n; i++) {
            cards[i] = sc.nextInt();
        }

        int maxSum = 0;

        // 브루트포스 방식으로 3장의 카드 합을 계산
        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++) {
                    int sum = cards[i] + cards[j] + cards[k];

                    // M을 넘지 않으면서 최대합을 찾기
                    if (sum <= m && sum > maxSum) {
                        maxSum = sum;
                    }
                }
            }
        }

        System.out.println(maxSum);  // 결과 출력
        sc.close();
    }
}

 

이거는 이것저것 보다가... 내 삼중포문이랑 비슷하지만 범위의 측면에서 저렇게 빼는게 중복을 제거할 수 있어서  더 좋겠다는 풀이를 봐서 적어본다....

 

브루트포스 알고리즘 별거아니네!