[JAVA] 백준 2798번: 블랙잭

 

---

문제

• N장의 카드가 주어질 때, 3장을 골라 M을 넘지 않으면서 M에 최대한 가까운 숫자 카드의 합을 구하는 문제.

 

아이디어

• 전형적인 브루트포스 문제로 모든 경우의 수를 파악한다.
• 3장을 골라야 하는게 고정이므로 3중 for 문 혹은 재귀문을 이용한다.
• 최대한 시간을 줄이기 위해 카드 3장의 합이 M일 경우 반복을 중단하고 종료한다.

 

풀이 1 (for 문 사용)

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] cards = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
        }

        int answer = 0;
        int diff = M;
        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];
                    if(sum == M) {
                        answer = sum;
                        System.out.println(answer);
                        return;
                    }
                    if(sum < M) {
                        if(M - sum < diff) {
                            answer = sum;
                            diff = M-sum;
                        }
                    }
                }
            }
        }
        System.out.println(answer);
    }
}

 

풀이 2 (재귀 사용)

import java.util.*;
import java.io.*;

public class Main {
    static int N, M;
    static int[] cards;
    static int answer = 0;
    static int diff = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        cards = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
        }

        recur(0, 0, 0);
        System.out.println(answer);
    }

    static void recur(int start, int depth, int sum) {
        if(sum > M) {
            return;
        }
        if(depth == 3) {
            if(sum == M) {
                answer = sum;
                diff = 0;
                return;
            }
            if(sum < M) {
                if(M - sum < diff) {
                    answer = sum;
                    diff = M-sum;
                }
            }
            return;
        }
        for(int i=start; i<N; i++){
            recur(i+1, depth+1, sum+cards[i]);
            if(diff == 0){
                return;
            }
        }
    }
}

 

채점 결과

for 문(위), 재귀(아래)

기타

•   재귀로 푸나 for 문으로 푸나 비슷하지만, 재귀 호출은 스택 메모리를 사용하는 만큼 for 문이 더 빠른 것을 알 수 있었다.

 

문제 링크

• 2798번: 블랙잭 (acmicpc.net)