백준 2798: 블랙잭에서 세 카드의 조합 찾기

백준 2798번 블랙잭은 세 카드의 합이 M을 넘지 않으면서 가장 커지는 경우를 찾는 문제입니다. 모든 조합을 확인하는 완전 탐색으로 풀었습니다.

같은 카드를 다시 뽑지 않도록 범위를 잡았습니다

세 반복문의 인덱스를 i < j < k로 둡니다. 첫 카드는 0부터 N-3까지, 두 번째 카드는 i + 1부터 N-2까지, 세 번째 카드는 j + 1부터 N-1까지 확인합니다. 이렇게 하면 같은 카드를 중복해서 고르지 않습니다. 순서만 다른 조합도 반복하지 않습니다.

카드의 수는 양수이므로 첫 카드만으로 M을 넘거나 앞의 두 카드 합이 M을 넘으면 해당 경우를 건너뜁니다. 세 카드의 합이 M 이하이고 지금까지 구한 값보다 크면 lastVal을 갱신합니다.

합이 M과 같을 때의 break는 세 번째 반복문만 끝냅니다. 바깥 반복문은 계속 실행되지만 답은 이미 M에 도달했으므로 더 커질 수 없습니다.

제출 코드

Java

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();
    }
}