[백준] 2798번: 블랙잭 (Java)

1. 문제설명

변형된 블랙책 규칙(양의 정수가 쓰여 있는 N장의 카드가 있을 때 플레이어는 N장의 카드 중에서 3장을 골라 이 카드의 합이 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.)으로 N장의 카드에 써져 있는 숫자가 주어졌을 때, 조건을 만족하는 카드 3장의 합을 구하는 문제이다.

• 시간 제한: 1초
• 메모리 제한: 128MB

 

2. 접근 방식

⇒ 완전탐색을 이용하여 모든 경우의 카드 3장의 합을 구한다.

• 카드를 배열에 저장하고, 3중 for문을 이용하여 모든 경우의 카드 3장의 합을 구한다.
• 카드 3장의 합을 구할 때 M을 넘지 않으면서 M에 최대한 가까운 값을 저장한다.

 

3. 최종 코드

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

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[] card = new int[N]; // 카드의 숫자를 배열에 저장
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            card[i] = Integer.parseInt(st.nextToken());
        }

        int result = 0; // 최종 결과
        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 = card[i]+card[j]+card[k]; // 현재 선택한 카드 3장의 합
                    // 현재 합이 M 이하이고 result 보다 크면 result 갱신
                    if(sum<=M && sum>result) result = sum;
                }
            }
        }
        System.out.println(result);
    }
}

 

4. 시간복잡도

3중 for문을 사용하고 있으므로 전체 시간복잡도는 $O(N^3)$ 이다.