[BOJ] 백준 17367번: 공교육 도박

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

17367번: 공교육 도박

---

주사위를 N번을 던져서 나온 최근 3개의 값으로 상금의 기대값을 구하는 문제입니다.

앞에서 몇번을 던져서 뭐가 나오든 신경을 쓸 필요없이 최근 3개의 눈을 기반으로 던질 수 있는 경우를 고려하면 쉽게 풀 수 있습니다.

만약 최근 3개가 5 3 4의 눈이 나왔다면, 현재 상금과 한번 더 던졌을때 다음에 올 눈 1~6에서의 기대값을 계속 구해가면서 더이상 던질 수 없을때 까지 반복하면 됩니다. 

#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>

using namespace std;
typedef long long ll;
int n;
int tmp[3];
double money[7][7][7] = { 0, };
double dp[7][7][7][1001]; // 최근 3개가 i j k 일때 s번 더 던질 수 있음
void dfs(int level) {
	if(level == 3) {
		int res = 0;
		if (tmp[0] == tmp[1] && tmp[0] == tmp[2]) {
			res = 10000 + tmp[1] * 1000;
		}
		else if (tmp[0] == tmp[1]) {
			res = 1000 + tmp[1] * 100;
		}
		else if (tmp[1] == tmp[2]) {
			res = 1000 + tmp[1] * 100;
		}
		else if (tmp[2] == tmp[0]) {
			res = 1000 + tmp[0] * 100;
		}
		else {
			res = max(tmp[0], max(tmp[1],tmp[2])) * 100;
		}
		money[tmp[0]][tmp[1]][tmp[2]] = (double)res;
	}
	else {
		for (int i = 1; i < 7; i++) {
			tmp[level] = i;
			dfs(level + 1);
		}
	}
}
double recv(int a, int b, int c, int remain) {
	if (!remain) {
		return money[a][b][c];
	}
	double& ret = dp[a][b][c][remain];
	if (ret > 0.0) return ret;
	ret = money[a][b][c];
	double cnt =0;
	for (int i = 1; i < 7; i++) {
		cnt += recv(b, c, i, remain - 1);
	}
	cnt /= 6;
	ret = max(ret, cnt);

	return ret;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	dfs(0);
	double ans = 0;
	memset(dp, -1.0, sizeof(dp));
	ans = recv(0, 0, 0, n);
	cout << fixed;
	cout.precision(7);
	cout << ans;
}