백준 2798 Java - 블랙잭

제목 : 블랙잭

---

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다.

카드의 합이 21 을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다.

블랙잭은 카지노마다 다양한 규정이 있다.

한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

김정인 버전의 블랙잭에서는 각 카드에 양의 정수가 쓰여 있다.

그 다음, 딜러는 N 장의 카드를 모두 숫자가 보이도록 바닥에 놓는다.

그런 후에, 딜러는 숫자 M 을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N 장의 카드 중에서 3 장의 카드를 골라야 한다.

블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M 을 넘지 않으면서, M 과 최대한 가깝게 만들어야 한다.

N 장의 카드에 써져 있는 숫자가 주어졌을 때,

M 을 넘지 않으면서 M 에 최대한 가까운 카드 3 장의 합을 구해 출력하시오.

입력

첫째 줄에 카드의 개수 N (3 <= N <= 100) 과, M (10 <= M <= 300,000) 이 주어진다.

둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000 을 넘지 않는 양의 정수이다.

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

예제 입력 및 출력

예제 입력	예제 출력
5 21 5 6 7 8 9	21
10 500 93 181 245 214 315 36 185 138 216 295	497

---

Brute Force 란 무엇일까?

가능한 모든 조합을 "전부" 결합하여, 결과에 대응하는 것을 의미한다.

사실 이 부분부터, 순열 (Sequence) 에 대한 이해와, 최대 근접 상황 시 행동 강령을 알아야 한다.

단계별로 풀어보기 순서대로 여기까지 왔다면, 사실상 이제부터가 시작이라고 생각이 들기도 한다.

먼저, 수학적인 의미에서의 집합까지 생각하지 말고,

우리가 이 문제에서 간단히 사용하게 될 집합의 개념 정도만 생각해보자 - 필자도 집합의 수학적인 개념은 잘 모른다.

1. 3 장의 요소를 고른다.
2. 순서는 상관이 없다. - (ex 5, 6, 7 or 6, 5, 7) 을 고르던, 집합은 동일하다.
3. 같은 요소를 2 번 고를 수는 없다.
4. 요소는 중첩되지 않지만, 점점 커지는 규칙을 가지고 있지는 않다.

사실상 문제 자체에서 "3개" 의 카드를 고르도록 정해져 있기 때문에,

아직 순열에서의 dfs 알고리즘을 사용 할 필요는 없다.

하지만, 동적 집합 개수에 대한 개념을 제외하더라도, 순서 상관이 없는 요소를 고르는 것을 고려해야 한다.

이 문제에 대한 해결법은 2 가지가 있다.

• 간단한 버전 - 직접 for or while 을 3 번 사용하여 브루트 포스 한다.
• 어렵지만, 곧 나오게 될 알고리즘을 미리 보게 될 dfs 방식

간단한 버전의 풀이법

문제에서 명시적으로 "3개" 의 카드를 선택하라고 했다.

이 경우, 우리는 for or while 을 선택하여 풀이하면 된다.

나는 for 을 사용하여 풀도록 하겠다 - while 과는 본질적으로 동일하므로.

그 전에, 순서 상관이 없다는 것을 프로그래밍적으로 어떻게 이해해야 할까?

한번 위의 입력 예제 5 6 7 8 9 에 대해서 3 개의 집합을 머릿속으로 만들어 보자.

1 번째 카드	2 번째 카드	3 번째 카드	중첩 여부
5	6	7	x
5	6	8	x
5	6	9	x
6	5	8	o (2 번째 요소와 중첩됨)
...	...	...	...

2 번째 레이블과, 4 번째 레이블은 중첩된다.

즉, 순서는 상관이 없다고 했으므로, (5, 6, 8) 이던, (6, 5, 8) 이던 동일하다는 것이다.

그렇다는 것은, (1번째 카드 인덱스) < (2번째 카드 인덱스) < (3번째 카드 인덱스) 를 의미한다.

우리는 입력 예제 5 6 7 8 9 에 대해서 1 차원 배열로 저장할 것이다.

• 1 번째로 고른 카드 인덱스 i 에 대해서, 2 번째로 고른 카드 인덱스 j 를 순회한다.
• 2 번째로 고른 카드 인덱스 j 에 대해서, 3 번째로 고른 카드 인덱스 k 를 순회한다.

이를 구현하는 것이 이번 문제의 관건이다.

즉, (i < j < k) 이다. (순서 상관없으며, 요소가 중첩되지 않는 집합.)

이를 구현하기 위해서, 간단한 방식으로 for 문을 3 번 중첩하면 된다.

Answer 1 - for 문을 중첩

이 문제와 같이, 적은 숫자 만큼 요소를 뽑아 모든 경우의 수를 알아볼 때 사용하는 방식이다.

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        // 주어지는 모든 카드의 개수 - 배열 크기 생성하면 됨.
        int N = Integer.parseInt(st.nextToken());
        // 딜러가 크게 외칠 숫자 - 3 개의 요소를 더했을 때, 가장 가까운 숫자를 구할 때 비교하게 됨.
        int M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());

        int[] cards = new int[N];

        for(int i = 0; i < N; i++)
            cards[i] = Integer.parseInt(st.nextToken());

        // 3 개를 뽑으므로. - 초기화
        int[] select = new int[3];

        // 가장 큰 수 - 초기화
        int max = -1;

        for (int i = 0; i < N; i++) { // 1 번째 카드 선택
            select[0] = cards[i];
            for (int j = i + 1; j < N; j++) { // 2 번째 카드 선택
                select[1] = cards[j];
                for (int k = j + 1; k < N; k++) { // 3 번째 카드 선택
                    select[2] = cards[k];

                    // 현재 선택한 3 개의 카드에 대해서 총합을 계산한다.
                    int sum = select[0] + select[1] + select[2];

                    // 만약 딜러가 말한 숫자보다, 현재 3 개 카드의 합이 더 크면 안된다는 규칙이 있었다.
                    if (sum > M) {
                        // 무시하고, 다른 카드의 조합을 찾는다.
                        continue;
                    } else {
                        // 현재까지 저장하고 있는 최대 값 보다, 
                        // 조합된 3 개의 카드 합이 더 크다면, 최대값을 최신화한다.
                        max = max < sum ? sum : max;
                    }
                }
            }
        }
        System.out.println(max);
    }
}

밑의 풀이 방식은 좀 나중에 다뤄지게 되므로, 아직 접하지 않은 DFS 문제를 어떻게 풀어야 할지,

궁금한 사람들이 보면 된다. "재귀" 라는 의미에 대해서 알아야 하기 때문이다.

---

DFS 방식의 풀이법

혹시 "재귀" 라는 말을 들어 본 적이 있는가?

재귀 란, 자기 자신을 호출(사용) 하는 행동을 의미한다.

이에 대해서 자세한 내용은

재귀에 대하여

를 참조하거나, 검색해 보길 바란다.

이 문제에서 재귀를 결합한다면, 우리가 dfs 메서드를 제작하며 고려해야 할 2 가지 요소가 있다.

1. 재귀 코드에서, 자기 자신의 코드를 호출 할 때, 입력값은 서로 달라야 한다.
2. 3 개의 요소를 선택하므로, 재귀의 깊이는 3 이다.

import java.util.*;
import java.io.*;

public class Main {
    // dfs 메서드에서 최대값을 업데이트 할 수 있도록 설정.
    public static int max = -1;

    // dfs 메서드에서 마지막 카드까지 골랐을 때, 규칙을 만족하는지 확인하기 위해.
    public static int M;

    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());
        M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());

        // 주어진 모든 카드를 담을 장소(배열)
        int[] cards = new int[N];

        for(int i = 0; i < N; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
        }

        // 선택된 3 개의 카드를 담을 저장소
        int[] select = new int[3];

        dfs(0, cards, select, 0);

        System.out.println(max);
    }
    static void dfs(int startIndex, int[] cards, int[] select, int deep) {
        if(deep == 3) {
            // 선택된 카드들에 대한 합
            int tempResult = sum(select);

            // 규칙을 지켰는지 확인하기 위해.
            if(tempResult > M)
                return;

            max = max < tempResult ? tempResult : max;

            // 3 개를 모두 선택했으므로, 밑의 로직은 실행하지 않는다. (IndexOutOfBounds 에러 예방)
            return;
        }

        for(int i = startIndex; i < cards.length; i++) {
            select[deep] = cards[i];

            dfs(i + 1, cards, select, deep + 1);
        }
    }

    static int sum(int[] select) {
        int sum = 0;
        for(int i = 0; i < select.length; i++)
            sum += select[i];

        return sum;
    }
}

메서드 재귀를 위해 따로 dfs(...) 함수를 제작했다.

사실 여기서 int[] cards, int[] select 두 개의 메서드 인자는 정적 변수로 선언해도 된다.

하지만, 재귀를 특성을 더 돋보이기 위해, 인자로 넣었다.

한번 dfs 메서드 내부의 인자의 의미를 살펴보자 :

• startIndex : 순서를 상관하지 않는 집합의 특성으로, 이전에 이미 선택되었던 카드는 신경 쓸 필요가 없다.
• int[] cards : 주어진 모든 카드의 정보를 담아두는 배열
• int[] select : 선택한 카드의 정보를 저장하는 배열
• int deep : 현재 선택할 카드의 순서를 저장하는 숫자. (0, 1, 2)
  • deep 이 3 이 된다면, select 배열이 모두 채워졌다는 의미이므로, 계산을 수행 할 시간이라는 뜻.