백준 4148 (31게임) - java

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

 

문제

31게임은 옛날 옛날에 기차를 타고 다니던 사기꾼들이 제일 좋아했던 게임이다. 이 게임은 24개의 카드로 이루어진 카드팩을 이용한다. 1,2,3,4,5,6이 쓰여진 카드가 4개씩 있다. 카드팩의 카드는 두명의 플레이어 모두가 볼 수 있다. 두명의 플레이어는 번갈아 가면서 카드팩에서 카드를 한장씩 가져온다. 그리고 카드를 같은 곳에 쌓아놓는다.

게임의 목표는 마지막 플레이어가 카드를 쌓았을 때 쌓여 있는 카드의 합이 31을 초과하지 않아야 한다는 것이다. 

상윤이는 두명의 플레이어가 선택한 카드의 순서가 주어졌을 때 최종적으로 우승하는 플레이어가 누구인지 결정하는 프로그램을 작성하려고 한다.

두 플레이어는 나머지 카드 중 자신이 이기기 위한 완벽한 전략을 사용한다고 가정한다.

예를 들어 플레이어 찬미와 아람이가 다음과 같은 순서로 카드를 뽑는다고 가정한다.

• 찬미 3
• 아람 5
• 찬미 6
• 아람 6
• 찬미 5
• 아람 6

이렇게 쌓아올리면 쌓여진 총 카드의 숫자들의 합은 31이 된다 다음 차례인 찬미가 무슨 카드를 뽑던지 31을 초과하여 찬미가 지고 아람이가 이기게 된다.

상윤이가 프로그램을 짤 수 있게 도와주자

 

유형 : 재귀

 

접근 방식

• 최선의 결과를 반복한다는 것은 무엇일까 ? 
  • 카드는 1, 2, 3, 4, 5, 6 총 6장이 있다. A가 해당 턴에 1로만 이길 수 있고 나머지 카드로는 이길 수 없다면 해당 턴에 A는 이긴 것일까 ?
  • 뭔 소린가 하겠지만 내가 하고 싶은 말은 사용할 수 있는 카드 중 1장으로라도 이길 수 있다면 이긴다는 것이다.
• 즉 6번의 반복문을 돌릴 것이다. 해당 카드로 해당 턴에 사용자가 이길 수 있다면 이기는 값을 반환하도록 재귀문을 짜면 된다.

 

전체 코드

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

public class Main {

    static char[] arr;

    static String line;
    static int n;
    static int[] num = new int[7];

    static int result;

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

        while(true) {
            line = br.readLine();

            if(line == null)
                break;

            arr = line.toCharArray();
            n = arr.length;
            boolean turn = true;
            result = 31;

            for(int i = 1 ; i <= 6 ; i++) {
                num[i] = 4;
            }

            for(int i = 0 ; i < n ; i++) {
                result -= arr[i] - '0';
                num[arr[i] - '0'] -= 1;
                turn = !turn;
            }

            char re = go(turn,result) == 1 ? 'A' : 'B';
            sb.append(line+" "+re+"\n");
        }

        System.out.print(sb);

        br.close();
    }

    static int go(boolean turn,int rest) {
        if(rest == 0) {
            if(turn) {
                return 2;
            }else {
                return 1;
            }
        }

        int result = 0;

        for(int i = 1 ; i <= 6; i ++) {

            if(num[i] >= 1 && rest - i >= 0) {

                int tmpRest = rest - i;

                if(turn) {
                    if(result == 0 || result == 2) {
                        num[i] -= 1;
                        result  = go(!turn,tmpRest);
                        num[i] += 1;
                    }
                }else {
                    if(result == 0 || result == 1) {
                        num[i] -= 1;
                        result  = go(!turn,tmpRest);
                        num[i] += 1;
                    }
                }
            }else {
                if(turn) {
                    if(result == 0 || result == 2) {
                        result = 2;
                    }
                }else {
                    if(result == 0 || result == 1) {
                        result = 1;
                    }
                }
            }
        }

        return result;
    }
}