[자바] 백준 2798번 블랙잭

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

 

[문제 이해]

브루트포스 문제임을 알면 쉽게 풀 수 있는데 브루트포스인지 아닌지 스스로 판별을 하기도 전에 문제 유형을 봐버려서 금방 해결 방법을 생각해냈다. 3장의 카드만 뽑는데 모든 경우에 대해서 다 탐색해서 가장 목표한 수에는 가깝지만 넘지는 않는 수를 만드는 방법을 찾으면 되는 문제였다.

 

[문제 풀이]

문제를 풀면서 굳이 3중 for문을 탈출하는 부분을 구현하겠다고 break 걸었다가 한 번 틀렸는데 이 부분을 제외하니까 바로 정답 처리가 됐다. 가장 첫 번째로 탐색하는 건(i) 처음부터 마지막에서 2번째까지만 탐색해도 되므로 for문에서 n-3까지만 돌면 됐고(0~n-3) 같은 원리로 두 번째 카드(j)는 n-1(i+1~n-2), 마지막 카드(k)는 끝까지 탐색하는 방식(j+1~n-1)으로 구현했다.

 

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[] arr = new int[n];

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

        int sum = 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++){
                    if(sum < arr[i] + arr[j] + arr[k] && arr[i] + arr[j] + arr[k] <= m){
                        sum = arr[i]+arr[j]+arr[k];
                    }
                }
            }
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(sum));
        bw.flush();
        bw.close();
    }
}