[백준] 블랙잭

본 게시글은 PC 환경에서 보기 편하도록 설정이 되어 있습니다.

블랙잭

브루트포스 로 분류되어있는 완전탐색류 문제입니다.

DFS를 아신다면 가장 기본적인 수준의 난이도에 해당하는 문제일 것 같습니다.

풀이순서는 아래 과정을 반복하면 간단하게 풀 수 있습니다.

1. 카드를 1장씩 모아 저장합니다.

2. 카드가 3장이 되면 합을 구합니다.

   2.1. 카드의 합이 목표 값보다 크다면 마지막 카드를 버리고 1번으로 돌아갑니다. 2-2. 카드의 합이 목표 값과 같다면 최대 값으로 저장후 게임을 종료시킵니다. 2-3. 카드의 합이 목표 값보다 작다면 현재 최대 값으로 알고있는 값과 비교하여 큰 값을 유지합니다.

3. 마지막 카드를 버리고 1번으로 돌아갑니다.

 

풀이 스타일

Java와 같은 객체지향 언어를 이용하여 알고리즘을 푼다면 객체지향스럽게 알고리즘을 풀어야 한다고 생각합니다.

단순한 알고리즘 풀이는 가독성은 당연히 떨어지고, Java를 쓰는 이유가 퇴색되는 것 같습니다.

따라서, Java를 이용해서 문제를 푸신다면 객체가 해야할 행동으로 문제를 풀 수 있도록 하시는 것을 추천드립니다.

 

카드의 값을 단순히 int 로 표현하지 않고 Value Object 즉, VO 인 Card 객체로 만들어 List 로 저장합니다.

현재 게임의 목표값과 사용자가 어떠한 카드를 가지고 있는지를 나타내기 위해 BlackJackGame 객체를 생성합니다.

BlackJackGame 객체는 사용자가 카드를 더하고, 버리고, 합을 구하는 등의 행위를 할 수 있는 메소드를 가지고 있습니다.

아래 코드를 보신다면 쉽게 이해가 되실것 같습니다.

 

코드

 

public class Main {
 
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int target = Integer.parseInt(st.nextToken()); // m
      
        List<Card> cards = Arrays.stream(br.readLine().split(" "))
                .map(Integer::parseInt)
                .map(Card::new)
                .collect(Collectors.toList());
 
        BlackJackGame game = new BlackJackGame(target);
 
        for (int i = 0; i < cards.size() - 2; i++) {
            List<Card> userCards = new ArrayList<>();
            userCards.add(cards.get(i));
            game.start(userCards);
            pickAnother(game, cards, i);
        }
 
        System.out.println(game.getMax());
    }
 
    private static void pickAnother(BlackJackGame game, List<Card> cards, int beforeIndex) {
        if (game.isReachTarget()) {
            return;
        }
 
        if (game.hasThree()) {
            game.changeMax();
            return;
        }
 
        for (int i = beforeIndex + 1; i < cards.size(); i++) {
            Card nextCard = cards.get(i);
            game.addCard(nextCard);
            pickAnother(game, cards, i);
            game.abandonCard(nextCard);
        }
    }
 
}
 
class Card {
 
    private Integer number;
 
    public Card(Integer number) {
        this.number = number;
    }
 
    public Integer getNumber() {
        return number;
    }
 
}
 
class BlackJackGame {
 
    private Integer target;
    private Integer max = -1;
    private List<Card> userCards;
 
    public BlackJackGame(Integer target) {
        this.target = target;
    }
 
    public Integer getMax() {
        return max;
    }
 
    public void start(List<Card> cards) {
        this.userCards = cards;
    }
 
    public boolean hasThree() {
        return userCards.size() == 3;
    }
 
    private int getSum() {
        return userCards.stream()
                .mapToInt(Card::getNumber)
                .sum();
    }
 
    private boolean isOver(int sum) {
        return sum > target;
    }
 
    public void changeMax() {
        int sum = getSum();
        if (isOver(sum)) {
            return;
        }
        if (sum > this.max) {
            max = sum;
        }
    }
 
    public void addCard(Card nextCard) {
        this.userCards.add(nextCard);
    }
 
    public void abandonCard(Card nextCard) {
        this.userCards.remove(nextCard);
    }
 
    public boolean isReachTarget() {
        return this.target.equals(this.max);
    }
}