[백준/JAVA] 2798 블랙잭

블랙잭

백준 2898번 블랙잭 문제 링크

풀이

• 3번의 카드를 뽑는다.
• 1번 카드 "i"는 0 ~ N-2
• 2번 카드 "j"는 i ~ N-1
• 3번 카드 "k"는 j ~ N
• 모든 경우의 수를 체크해야하므로 브루트포스 알고리즘 방식으로 진행
• 세 카드의 합이 M보다 크지 않고 가장 가까운 값을 구한다.

---

제출 코드

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st;
        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;
        int lastVal = 0;
        for (int i = 0; i < N - 2; i++) {
            // 첫 번째 카드가 M보다 크면 다른 카드 부터 시작
            if (arr[i] > M) {
                continue;
            }
            for (int j = i + 1; j < N - 1; j++) {
                // 첫 번째 카드와 두 번째 카드의 합이 크다면 다른 두 번쨰 카드 부터 시작
                if (arr[i] + arr[j] > M) {
                    continue;
                }
                for (int k = j + 1; k < N; k++) {
                    sum = arr[i] + arr[j] + arr[k];
                    // 세 카드의 합이 원하는 M값과 같다면 루프 중지
                    if (sum == M) {
                        lastVal = sum;
                        break;
                    }
                    // 마지막 값 < 세 카드의 합 < M 이면 마지막 값 최신화
                    if (lastVal < sum && sum < M) {
                        lastVal = sum;
                    }
                }
            }
        }
        bw.write(String.valueOf(lastVal));
        bw.flush();
    }
}

---