블랙잭 알고리즘으로 M에 가까운 카드 조합 찾기

블랙잭 게임 알고리즘: M에 최대한 가까운 카드 조합 찾기

안녕하세요, 프로그래밍에 관심이 많은 여러분! 오늘은 블랙잭 게임을 변형한 문제를 해결해보겠습니다. 이 문제는 주어진 카드에서 세 장의 카드를 선택해 그 합이 특정 숫자 M을 넘지 않으면서 M에 최대한 가까운 합을 찾는 것입니다.

이 문제를 해결하기 위해 브루트 포스 알고리즘을 사용할 것입니다. 브루트 포스(Brute Force)는 모든 가능한 경우의 수를 따져보는 방법으로, 100% 정확성을 자랑하지만 시간이 오래 걸리는 단점이 있습니다. 그렇기 때문에 간단한 문제에서는 매우 유용합니다.

문제 이해하기

블랙잭 게임과 같은 규칙을 가지고 있습니다. 딜러는 N장의 카드를 바닥에 놓고, 플레이어는 제한된 시간 안에 이 카드들 중 3장을 선택합니다. 그 선택의 카드들의 합이 M을 넘지 않는 동시에 M에 가장 가깝길 원합니다.

입력

• 첫 번째 줄에 카드의 개수 N과 목표 숫자 M이 주어집니다.
• 두 번째 줄에는 카드에 적힌 양의 정수가 주어집니다.

여기서 각 숫자는 100,000을 넘지 않는 값입니다. 조건은 다음과 같습니다:

• 3 ≤ N ≤ 100
• 10 ≤ M ≤ 300,000

결과적으로, 세 장의 카드의 합이 M을 넘지 않으면서 M에 가장 가까운 값을 출력해야 합니다.

해결 방법

문제를 해결하기 위한 방법은 다음과 같은 접근 방식입니다:

1. 카드 값을 배열에 저장합니다.
2. 3중 반복문을 사용하여 모든 카드 조합을 시도합니다.
3. 각 조합의 합이 M보다 작거나 같도록 조건을 설정합니다.
4. 조건을 만족하는 경우, 그 합을 기록합니다.
5. 가장 가까운 값을 최종적으로 출력합니다.

코드 작성하기

이제 위 내용을 기반으로 코드를 작성해 보겠습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Q2798 {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        StringTokenizer st2 = new StringTokenizer(bf.readLine(), " ");

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] card = new int[n];
        int min = 0;  // 조건을 만족하는 가장 큰 합
        int sum;      // 세 카드의 합
        int result = 0; // 최종 결과

        for (int i = 0; i < n; i++) {
            card[i] = Integer.parseInt(st2.nextToken());
        }

        // 3중 반복문으로 모든 조합 계산
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int h = j + 1; h < n; h++) {
                    sum = card[i] + card[j] + card[h];

                    // 조건을 만족하는 경우 업데이트
                    if (sum <= m && sum > min) {
                        min = sum; // M에 가장 가까운 합
                        result = sum; // 최종 결과에 저장
                    }
                }
            }
        }

        System.out.println(result); // 결과 출력

        bf.close();
    }
}

코드 설명하기

1. 입력 처리: BufferedReader를 사용하여 카드의 개수와 목표 합을 입력받습니다.
2. 배열 초기화: 카드값을 배열에 저장합니다.
3. 3중 반복문: 각 카드 조합을 찾기 위해 세 개의 반복문을 사용합니다.
4. 조건 검사 및 결과 갱신: 현재의 카드 합이 M 이하이고 이제까지 찾은 가장 큰 값보다 클 경우, 그 값을 갱신합니다.
5. 결과 출력: 최종적으로 M에 가장 가까운 카드 합을 출력합니다.

마무리하며

블랙잭 게임을 변형한 이번 문제를 통해 브루트 포스 알고리즘의 사용법을 알아보았습니다. 다소 시간이 오래 걸리는 방법이지만, 간단한 문제를 해결하기에는 충분히 효과적입니다. 앞으로 더 복잡한 문제들을 해결하는 데에도 도움될 것입니다.

여러분도 다양한 문제를 풀어보며 프로그래밍 실력을 쌓아보세요! 질문이나 의견이 있다면 댓글로 남겨주세요. 다음 포스팅에서 만나요!