[백준] 블랙잭 2798

코드 힌트

1. 입력 값을 처리하기:
   • nextLine()을 사용해 입력 값을 한 줄씩 읽어오고, split()을 사용해 공백을 기준으로 분리합니다.
2. 첫 번째 입력 값 처리:
   • 첫 번째 입력 값은 카드의 개수와 카드 합의 최댓값을 나타냅니다.
3. 두 번째 입력 값 처리:
   • 두 번째 입력 값은 각 카드의 숫자를 나타냅니다.
4. 조합을 구하기:
   • 주어진 카드 숫자들로 조합을 구합니다. 이를 위해 백트래킹 또는 재귀함수를 사용합니다.
5. 최댓값 계산:
   • 조합의 합이 주어진 최댓값을 넘지 않는 경우, 그 중에서 가장 큰 합을 찾습니다.

 

---

정답은 더보기 클릭

import java.util.*;

public class Main {
    // 조합의 합 중 최대 값을 저장할 변수
    static int maximum = 0;
    // 카드 합의 최댓값
    static int maxNum = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 첫 번째 입력을 한 줄로 읽어 공백으로 분리
        String input1 = sc.nextLine();
        String[] str = input1.split(" ");
        
        // 카드 개수
        int cardCount = Integer.parseInt(str[0]);
        // 카드 합의 최댓값
        maxNum = Integer.parseInt(str[1]);
        
        // 두 번째 입력을 한 줄로 읽어 공백으로 분리하여 카드 숫자를 배열에 저장
        int[] cardArr = new int[cardCount];
        String input2 = sc.nextLine();
        String[] cards = input2.split(" ");
        for (int i = 0; i < cardCount; i++) {
            cardArr[i] = Integer.parseInt(cards[i]);
        }
        
        // 각 카드를 방문했는지 여부를 저장하는 배열
        boolean[] visited = new boolean[cardCount];
        
        // 카드 조합을 구하기 위한 함수 호출
        combination(cardArr, visited, 0, cardCount, 3);
        
        // 최댓값 출력
        System.out.println(maximum);
    }
    
    // 카드 배열에서 r개의 조합을 구하는 함수
    public static void combination(int[] cardArr, boolean[] visited, int start, int n, int r) {
        // r개의 조합을 모두 선택한 경우
        if (r == 0) {
            isMaximum(cardArr, visited, n);
            return;
        }
        
        // start부터 n까지의 요소를 순회하며 조합을 구함
        for (int i = start; i < n; i++) {
            visited[i] = true;
            combination(cardArr, visited, i + 1, n, r - 1);
            visited[i] = false;
        }
    }
    
    // 선택된 카드 조합의 합이 최대 값을 넘지 않는지 확인하는 함수
    public static void isMaximum(int[] cardArr, boolean[] visited, int n) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                sum += cardArr[i];
            }
        }
        // 합이 maxNum 이하인 경우 최대 값을 업데이트
        if (sum <= maxNum) {
            maximum = Math.max(sum, maximum);
        }
    }
}