[백준 2798번] 블랙잭 문제 - Java

 

완전 탐색 알고리즘)

주어진 조건을 모두 비교해서 답을 찾는 기법으로, 재귀함수를 통해서 해당 문제를 해결해보았습니다.

 

첫 번째 시도)

아래의 코드를 백준에 제출한 결과로 런타임 오류가 출력되었습니다.

시간 제한과 주어진 숫자의 최대 개수를 고려했을 때, 정수의 합을 구하는 반복문 구절에서 제한시간을 넘긴 것 같았습니다.

 

import java.util.Scanner;

public class blackjack_2798 {
    static int N = 0, M = 0;
    public static void main(String[] args) {
        int black = -9999;
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();				// 입력받을 정수들의 개수
        M = sc.nextInt();				// 최대 합
        int[] arr = new int[N];				// 사용자로부터 입력받은 정수들
        int[] buf = {0, 0, 0};				// 선택된 정수를 임시로 저장

        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }
        System.out.println(solve(arr, buf, -1, 0));

    }
    public static int solve(int[] arr, int[] buf, int idx, int cnt) {
        int answer = -999;
        int temp = 0;
        if (cnt >= 3) {					// 3개의 정수를 선택했을 때
            int sum = 0;
            for (int val : buf) {
                sum += val;				// 그들의 합을 구함
            }
            return sum;
        }
        for (int i = idx + 1; i < N; i++) {
            buf[cnt] = arr[i];
            temp = solve(arr, buf, i, cnt + 1);
            if (temp <= M && answer < temp)		// 반환된 합이 M보다 작거나 같고, answer에 저장된 값이 temp보다 작을 때
                answer = temp;
        }
        return answer;
    }
}

 

두 번째 시도)

cnt의 값이 3이 되었을 때 버퍼(buf)에 저장된 값을 더하는 for문 구절을 삭제했습니다.

버퍼(buf)를 매개변수로 넘기는 방법 대신에 정수들의 합을 넘기는 방식으로 수정하였습니다.

입력된 정수들 중에서 하나를 선택하면 sum 변수에 더하고, 이를 매개변수로 넘깁니다.

 

import java.util.Scanner;

public class blackjack_2798 {
    static int N = 0, M = 0;
    public static void main(String[] args) {
        int black = -9999;
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();			// 입력받을 정수들의 개수
        M = sc.nextInt();			// 최대 합
        int[] arr = new int[N];			// 사용자로부터 입력받은 정수

        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }
        System.out.println(solve(arr, 0, -1, 0));

    }
    public static int solve(int[] arr, int sum, int idx, int cnt) {
        int answer = -999;
        int temp = 0;
        if (cnt >= 3) {
            return sum > M ? 0 : sum;
        }
        for (int i = idx + 1; i < N; i++) {
            temp = solve(arr, sum+arr[i], i, cnt + 1);
            if (answer < temp)
                answer = temp;
        }
        return answer;
    }
}

 

정리)

모든 결과를 비교해서 답을 찾아내는 완전 알고리즘의 특성상, 배열에 저장된 정수들의 합을 구하는 반복문 조차 제한시간을 초과할 수 있다는 사실을 알 수 있었습니다.