[BaekJoon] #2798 블랙잭

문제이해

입력

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

문제접근

• 브루트포스 알고리즘은 완전탐색알고리즘으로 모든 경우의 수를 탐색하면서 결과를 찾는 알고리즘입니다.
• 이 문제는 배열을 생성해서 모든 배열을 탐색하며 result 변수를 조건에 맞게 초기화해가면서 결과값을 찾으면 됩니다.

값을 분리하기 위해 StringTokenizer를 선언해주었습니다.

• StringTokenizer는 한번 생성된 이후에는 그 문자열에 대해서만 토큰화합니다.
• 입력이 두개로 나누어져 있으므로, 첫번째 입력에 N과 M을 입력받고, StringTokenizer객체를 한번 더 생성하여 입력한 값들을 토큰화하여 배열안에 넣어주었습니다.

삼중for문을 통해 배열을 전부 탐색하며 조건에 맞는 result값을 초기화시켜주었습니다.

• 첫 번째 카드를 선택한 후, 최소 두 장의 카드가 더 필요하기 때문에 남아 있는 카드의 수가 최소 2장이어야 하기 때문에, i의 범위는 0부터 N-2입니다.
• j는 항상 첫번째 카드 i 이후의 카드이여야 하고, 세번째 카드가 선택할 한장을 제외한 나머지의 범위를 가져야 하므로, j의 범위는 i+1부터 N-1까지입니다.
• 같은 방법으로, 마지막 카드 k의 범위는 j+1부터 N까지입니다.

이후엔 if문을 이용해 문제에 맞게 조건을 세우고, result값을 초기화해주면 됩니다.

code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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());
        }
        System.out.println(result(arr,N,M));
    }
    static int result(int[] arr, int N, int M){
        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 temp = arr[i]+arr[j]+arr[k];

                    if(M==temp){
                        return temp;
                    }

                    if(result < temp && temp < M){
                        result = temp;
                    }
                }
            }
        }
        return result;
    }

}