[BaekJoon/백준] 2798번

문제 이름은 블랙잭.

카테고리는 브루트포스이긴 한데, 세세하게는 재귀함수를 이용한 조합 뽑기라고 보면 된다.

 

뽑는 모든 경우의 수를 구한 뒤 뽑은 숫자를 더해주고, 이 값들 중 문제에서 주어진 값보다 크지않은 값 중 가장 가까운 값을 출력하는 문제다.

 

BufferedWriter와 BufferedReader를 이용하는 것이 더 프로그램적으로 효율적이나,

가독성을 위해 Scanner와 System.out.print를 사용한 코드를 올립니다.

import java.util.Scanner;

public class Main {
    static int N, M;
    static int[] arr;
    static boolean[] arr_b;
    static int max=0;
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);

        N = scanner.nextInt();
        M = scanner.nextInt();

        arr = new int[N];
        arr_b = new boolean[N];

        for(int i=0; i<N; i++) {
            arr[i] = scanner.nextInt();
        }
        BlackJack(0, 1);
        System.out.print(max);
    }

    public static void BlackJack(int index, int count) {
        if(count==4) {
            int k = calculate();
            if(M - k < M - max && k<=M)
                max=k;
            return;
        } else {
            for(int i=index; i<arr.length; i++) {
                if(arr_b[i])
                    continue;
                else {
                    arr_b[i]=true;
                    BlackJack(i+1, count+1);
                    arr_b[i]=false;
                }
            }
        }
    }
    public static int calculate() {
        int total=0;
        for(int i =0; i < N; i++) {
            if(arr_b[i])
                total+=arr[i];
        }
        return total;
    }
}

 

입력받은 값들을 다 알아서 제자리에 넣어주고, 중요한 부분은 BlackJack(0, 1) 함수가 호출되는 부분이다.

 

첫 BlackJack 함수에서, 배열의 크기만큼 포문을 돌면서 한자리를 뽑아준다 (뽑은 자리는 true로 표시)

그리고 두번째 BlackJack 함수를 호출하며 재귀를 구현한다. 두번째 BlackJack함수에서는 이전에 뽑은 자리수 이후 자리부터 다시 포문을 돌면서 뽑히지 않은 부분을 뽑는다.

 

이렇게 뽑기 과정이 세번 진행된 뒤, 네번째로 호출되는 재귀함수는 if문에서  뽑은 자리들을 체크하여 계산작업과 비교작업만 해준 뒤 리턴한다.

 

다시 세번째 재귀함수로 돌아가 포문을 돌면서 뽑지 않은 자리들을 뽑을 것이고(배열의 크기만큼) 다 뽑은 경우 세번째 재귀함수는 종료되고

다시 두번째 재귀함수가 다음 자리수를 뽑은 뒤 또 세번째 재귀함수를 호출한다. 이러한 과정에서 뒤를 돌아보지 않으며 뽑는다는것이 조합의 가장 큰 특징이다.

 

---

2021.03.06

 

문제를 다시봤다.

문제 카테고리가 브루트포스 카테고리이다.

 

이전에 풀었을 때는 백트래킹 류의 재귀함수 방법으로 문제를 풀었었다.

 

다른 사람들의 풀이를 많이 참고해보니, 반복문을 사용한 브루트포스 방향으로 풀더라..!!

 

그래서 반복문을 사용해서도 풀어봤고, 이전에 풀었던 재귀 방식으로도 다시 풀어보았다.

 

 

브루트포스 반복문

#include <stdio.h>

int N;
int MAX;
int C_MAX = 0;
int arr[100];

int main() {
    int temp;

    scanf("%d %d", &N, &MAX);

    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++) {
                temp = arr[i] + arr[j] + arr[k];

                if(MAX >= temp && C_MAX < temp)
                    C_MAX = temp;
            }
        }
    }

    printf("%d", C_MAX);


}

 

 

 

백트래킹 재귀함수

#include <stdio.h>

int N;
int MAX;
int C_MAX = 0;
int arr[100];
int arr_b[100];

// in 시작, c 갯수
void BlackJack(int in, int c) {
    
    // 세개 뽑고, 네번째 호출시.
    if(c == 4) {
        int result = 0;
        for(int i = 0; i < N; i++) {
            if(arr_b[i])
                result += arr[i];
        }
        if(MAX >= result && C_MAX < result)
            C_MAX = result;
        return;
    }
    
    for(int i = in; i < N; i++) {
        if(arr_b[i])
            continue;
        arr_b[i] = 1;
        BlackJack(i + 1, c + 1); // 여태 in + 1였는데도 통과 ㅋㅋ 최댓값을 구하는 거라 중복은 안걸렸나보다.
        arr_b[i] = 0;
    }
}

int main() {
    
    scanf("%d %d", &N, &MAX);
    
    for(int i = 0; i < N; i++)
        scanf("%d", &arr[i]);
        
    BlackJack(0, 1);
    
    printf("%d", C_MAX);
}

 

 

 

두 방법을 비교해보니, 확실히 반복문 방식이 코드도 짧고 속도도 빨랐다.