블랙잭

제출코드

없음. ㅠㅠ 3중 반복문 너무 싫어~

모범답안

import java.io.*;
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());

        StringTokenizer st2 = new StringTokenizer(br.readLine());
        int[] numbers = new int[N];
        for (int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(st2.nextToken());
        }

        int result = search(numbers, N, M);
        System.out.println(result);
    }

    static int search(int[] arr, int N, int M) {
        int result = 0;

        // 3개를 고르기 때문에 첫번째 카드는 N - 2 까지만 순회
        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++) {

                    // 첫 번째 카드가 M 보다 크면 skip
                    if (arr[i] > M) continue;

                    // 3개 카드의 합 변수 temp
                    int temp = arr[i] + arr[j] + arr[k];

                    // M과 세 카드의 합이 같다면 temp return 및 종료
                    if (M == temp) {
                        return temp;
                    }

                    // 세 카드의 합이 이전 합보다 크면서 M 보다 작을 경우 result 갱신
                    if (result < temp && temp < M) {
                        result = temp;
                    }
                }
            }
        }
        return result;
    }
}

배운점

• 사실 엄청 쉬운 문제인데 항상 N중 반복문 만드는 법을 까먹어서 문제다. 이번엔 제발 기억하자!!!!!!!!!!!!!!!

• 3중반복문이기 때문에 첫번째 인자는 i=0 -> j=i+1 -> k = j+1로 설정하면된다.
  당연하게도 시작 위치가 각 인자에 1을 더한 값이기 때문이다.

• 첫 번째 루프 (i = 0; i < N - 2; i++): 마지막 두 요소의 자리를 남겨두어야 하므로 N-2까지 반복한다. 만약 N-1 또는 N까지 간다면, 두 번째와 세 번째 요소를 선택할 수 있는 공간이 없게 된다.

• 두 번째 루프 (j = i + 1; j < N - 1; j++): 첫 번째 요소가 이미 선택되었기 때문에, i+1부터 시작한다. 마지막 요소의 자리를 남겨두어야 하므로 N-1까지 반복한다. 만약 N까지 간다면, 세 번째 요소를 선택할 수 있는 공간이 없게 된다.

• 세 번째 루프 (k = j + 1; k < N; k++): 첫 번째와 두 번째 요소가 이미 선택되었기 때문에, j+1부터 시작한다. 여기서는 세 번째 요소가 마지막 요소가 될 수 있으므로 N까지 반복한다.

• 이제는 제발 외우자~
  첫번째 인자는 오름차순 더하기, 두번째 인자는 내림차순 빼기

• 마지막으로 하나만 기억하자.

위 브루트 포스 알고리즘의 경우 세 카드의 합이 M 이랑 같지 않는 이상 모든 경우의 수를 탐색한다. 즉 최악의 경우 수행시간이 O(N3) 이 된다.
그렇기에 조금만 더 효율적으로 탐색하기 위해서 어떻게 해야할지 고민해볼 가치가 있다.
조건을 보면 세 카드의 합이 M 을 넘으면 안된다는 조건이 있다.
그렇다면 카드 한 장이 이미 M 보다 크면 탐색할 필요가 있는가? 당연 없다.

만약 첫 번째 카드가 M 보다 작거나 같은 경우라도, 두 번째 카드를 선택 했을 때 두 카드의 합이 M 보다 커도 이미 탐색할 가치는 없을 것이다. (카드의 값은 양의 정수로 입력된다고 이미 조건에 나와있으므로)
이를 조건문으로 달아서 탐색하면 불필요한 탐색까지 할 필요가 없어질 것이다.
(물론 블랙잭 문제의 경우 데이터 자체가 매우 적어서 조건문을 다는 것이 시간을 더 지연시킬 수도 있다)

// 첫 번째 카드가 M 보다 크면 skip
if (arr[i] > M) continue;

출처 및 참고: https://st-lab.tistory.com/97