백준 17367번: 공교육 도박 (Java)

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

17367번: 공교육 도박

 

 

 

 

 

 

 

---

 

풀이

dp[i][j][k][n]을 '처음 주사위를 3번 던져 나온 눈이 i, j, k이고, 던질 수 있는 기회가 n번 남았을 때의 기댓값'이라고 정의합니다.

그러면 

dp[i][j][k][n] = max((주사위를 한 번 더 던지고, 기회가 n-1번 남았을 때의 기댓값), (i, j, k일 때의 점수))가 됩니다.

 

자세한 풀이는 에디토리얼를 참고하세요

 

 

코드

import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        double ans = 0;
        double[][][][] dp = new double[7][7][7][N];        
        
        for (int i = 1; i <= 6; i++) {
            for (int j = 1; j <= 6; j++) {
                for (int k = 1; k <= 6; k++) {
                    dp[i][j][k][0] = calc(i, j, k);
                }
            }
        }
        
        for (int n = 1; n <= N-3; n++) {
            for (int i = 1; i <= 6; i++) {
                for (int j = 1; j <= 6; j++) {
                    for (int k = 1; k <= 6; k++) {
                        double temp = 0;
                        for (int l = 1; l <= 6; l++) {
                            temp += dp[j][k][l][n-1] / 6;
                        }
                        dp[i][j][k][n] = Math.max(temp, dp[i][j][k][0]);
                    }
                }
            }
        }
        
        for (int i = 1; i <= 6; i++) {
            for (int j = 1; j <= 6; j++) {
                for (int k = 1; k <= 6; k++) {
                    ans += dp[i][j][k][N-3]/216;
                }
            }
        }
        System.out.println(ans);
    }
    
    static int calc(int i, int j, int k) {
        if (i == j && j == k) {
            return 10000 + i*1000;
        }
        if (i == j || j == k || k == i) {
            return 1000 + 100*(i+j+k - (i^j^k))/2;
        }
        return Math.max(Math.max(i, j), k) * 100;
    }
}