백준 - 2798 블랙잭

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

2798번: 블랙잭

 

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.

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

김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

 

입력

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.

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

 

출력

첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

 

---

풀이 방법

이 문제도 다행히? 한번에 해결하였다. 비록 브론즈 문제긴 하지만 그래도 나름 점점 실력이 늘긴하는구나...라는걸 느낄 수 있었던 문제!

 

어렵게 생각하지말고 DFS 로 풀자 이때 주의해야할 점은 아래와 같다.

1. dfs 시 합계에 해당하는 변수가 m 보다 작은 경우, 큰 경우, 동일한 경우를 계산해야한다. 나는 sum 이 m 보다 작거나 같을때 최댓값을 계산해서 result 에 저장하고, 클때는 그냥 0 을 return 했다.

 

2. 카드 3개를 뽑아야한다! 즉 2개의 카드 합으로 m 이 나오면 안되고, 꼭 3개를 뽑아야한다는 점이다. 이 때문에 sum == m 일 때도 cnt 가 3인지 확인을 해서 3 일 때만 result 의 값을 변경하는 계산을 하도록 코드를 구현하였다.

 

나머지는 주석 참고!

package baekJoon;

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

public class Quiz_2798 {
    static int n, m;
    static int result = Integer.MIN_VALUE;

    // 입력받은 카드 배열
    static int[] arr;
    // 합계를 위해 방문한 카드를 체크하기 위한 배열
    static boolean[] chk;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[n];
        chk = new boolean[n];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(findNum(arr, 0, 0));


    }

    // 이 문제에서 중요한 것은 카드를 꼭 3개를 뽑아야하고
    // 3개의 카드의 합이 m 보다 작을때, 클때, 같을 때를 나눠서 계산해야한다는 점이다.
    static int findNum ( int[] arr, int sum, int cnt){

        // sum 값이나 cnt 값이 각각 m 보다 크거나, 3 보다 크다면(3보다 큰 경우는 4개 이상의 카드의 합을 계산하는 경우임으로)
        if (sum > m || cnt > 3) {
            // 0 을 return
            return 0;

            // 만약 sum 이 m 과 동일하고, 동시에 cnt == 3 과 동일하다면
            // 즉 sum 으로 블랙잭이 나오고, 카드를 3개를 뽑은 경우라면
            // result 에 sum 을 담아서 return
        } else if (sum == m && cnt==3) {
            result = sum;
            return result;

            // 만약 sum 이 m 보다 작은데 카드는 3개를 봅은 경우라면
            // sum 과 result 를 비교해서 result 담아서 return
        } else if (sum < m && cnt == 3) {

            result = Math.max(sum, result);
            return result;

        } else {
            // cnt 가 3 이 안된 경우라면 for 문 진행
            for (int i = 0; i < n; i++) {
                // chk[i] 가 false 경우만 해당 카드의 숫자를 뽑는다
                if (!chk[i]) {
                    // chk[i] 번째 즉, arr[i] 번째 카드에 방문하면 방문했다고 표시하고,
                    chk[i] = true;
                    // sum 에는 현재 카드를 더하고, cnt 는 +1 한다.
                    findNum(arr, sum + arr[i], cnt+1);
                    // DFS 에서 빠져나왔다면 chk[i] 카드, arr[i] 카드를 false 로 바꾼다.
                    // 이는 추후 동일한 카드에 다시 방문할 수 있도록 하기 위함이다.
                    // 예를들어 뽑은 카드가 5,6,7 이라면 이 카드가 계속 true 인 상태가 아니라 false 여야만
                    // 추후 6,7,8 로 다시 합계를 계산할 수 있기 때문!!
                    chk[i] = false;

                }
            }
        }

        return result;
    }
}

 

중간에 틀렸습니다 한번은 result = 0 으로 고정시켜서ㅠㅠ // 시간이 줄어드나 다시 해봤는데 아니더라ㅠ