[알고리즘-자바] 백준 2798번 블랙잭

문제

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

2798번: 블랙잭

언어

자바 JAVA

정답 코드

i번째 카드와 j번째 카드를 고정시켜 두 카드의 합을 구한 다음 나머지 카드들을 하나씩 확인하면서 m보다 작지만 가장 큰 숫자를 저장하면 된다.

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);

        int[] arr = new int[n];
        input = br.readLine().split(" ");
        for (int i = 0; i < input.length; i++) {
            arr[i] = Integer.parseInt(input[i]);
        }

        Arrays.sort(arr);

        // m보다 작으면서 가장 큰 값을 저장
        int max = -1;
        // i는 세 카드 중에서 가장 숫자가 큰 카드, j는 i번째 카드 바로 앞 카드
        int i = n - 1;
        int j = i - 1;

        // i가 2보다 작으면 안 된다 -> 최소 3장의 카드는 골라야하기 때문.
        while (i >= 2) {
            // i번째 카드와 j번째 카드의 숫자 합
            int sum = arr[i] + arr[j];
            // k는 j번째 카드보다 앞에 있는 카드들
            for (int k = j - 1; k >= 0; k--) {
                if (sum + arr[k] <= m) {
                    // 최대 값을 저장한다.
                    max = Math.max(sum + arr[k], max);
                }
            }

            // i, j번째 카드를 다 돌았으므로 j번째 순서를 한 칸 앞당긴다.
            j -= 1;
            // j번째 카드를 다 돌았으므로 i번째 카드를 한 칸 앞당기고, j번째 카드는 i번째 카드 바로 앞에 위치시킨다.
            if (j == 0) {
                i -= 1;
                j = i - 1;
            }
        }

        System.out.println(max);
    }
}

틀린 코드

카드를 정렬하고 가장 뒤에서부터 하나씩 확인하여 m보다 작거나 같은 숫자가 나오는 즉시 출력하고 종료하는 코드를 작성했는데 이는 잘못된 코드였다. 뒤로 갈수록 숫자가 큰 카드이므로 뒤에서부터 합을 구하여 m보다 작거나 같으면 그것이 합이 가장 큰 줄 알았는데 아니었다.

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);

        int[] arr = new int[n];
        input = br.readLine().split(" ");
        for (int i = 0; i < input.length; i++) {
            arr[i] = Integer.parseInt(input[i]);
        }

        Arrays.sort(arr);

        int i = n - 1;
        int j = i - 1;

        while (i >= 2) {
            int sum = arr[i] + arr[j];
            for (int k = j - 1; k >= 0; k--) {
                if (sum + arr[k] <= m) {
                    // 잘못된 로직
                    System.out.println(sum + arr[k]);
                    return;
                }
            }

            j -= 1;
            if (j == 0) {
                i -= 1;
                j = i - 1;
            }
        }
    }
}