[BOJ] 백준 17367. 공교육 도박 (Platinum V)

예전에 UCPC 연습용으로 풀다가 해결하지 못한 문제이다.

기댓값 표현이 겁을 한사발 먹게 해주기도 했고, 그 때 당시 dp를 어려워했기 때문이 아닐까 생각된다.

문제는 아래와 같다.

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

17367번: 공교육 도박

---

의식의 흐름 및 해설

먼저, 주사위값마다 행동에 영향을 끼치는 것은 확실하다.

마침, 주사위도 최근 3개의 결과만 영향을 미치기 때문에 dp[100000+1][6+1][6+1][6+1]의 재귀 탑다운dp로 접근해볼 수 있을 듯하다.

 

여기서 멈추는 것이 나을지, 아니면 다음 결과를 진행하는 것이 좋을지는 max(현재, dp식) 으로 처리해주면 될 듯하다. 사실 이 부분도 꽤나 오래 고민했는데, dp가 결국 다음 결과중에서 최선의 값을 return할 것이기 때문에 위와 같이 나타내주면 된다. 이것이 바로 재귀의 위력이다 ㅎㅎ

 

다음 결과를 진행할 때 표시하는 dp식은 현재 주사위 결과가 n1, n2, n3라 할 때, dp(cur-1, n2, n3, i)로 나타내주면 될 것 같고, i는 1~6까지 모두 가능할 것이다.

기댓값을 구하는 것이기 때문에 1~6까지 나올 확률은 동등하므로 1~6까지의 dp식을 모두 더해서 6으로 나눈 값과 현재 선택의 결과를 비교해주면 될 듯하다.

 

주의할 점은, 답에 소수가 가능하기 때문에 double형으로 설정하였으며, 이 때 dp table을 -1로 memset하지 못하기 때문에 따로 방문체크여부 배열을 만들어주었다.

---

코드

#include <bits/stdc++.h>
using namespace std;
const int MAX=1003;
double n,d[MAX][7][7][7];
bool vis[MAX][7][7][7];
double score(int n1,int n2,int n3){
	if(n1==n2&&n2==n3)return 10000+1000*n1;
	else if(n1==n2||n1==n3)
	    return 1000+n1*100;
	else if(n2==n3)return 1000+n2*100;
	return 100*max({n1,n2,n3});
}
double dp(int cur,int n1,int n2,int n3){
	if(!cur)return score(n1,n2,n3);
	double&ret=d[cur][n1][n2][n3];
	if(vis[cur][n1][n2][n3])return ret;
	vis[cur][n1][n2][n3]=true;
	ret=score(n1,n2,n3);
	double tmp=0;
	for(int i=1;i<=6;i++){
		tmp+=dp(cur-1,n2,n3,i);
	}
	ret=max(ret,tmp/6);
	return ret;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin>>n;
	cout<<fixed;
	cout.precision(16);
	double ret=0;
	for(int i=1;i<=6;i++){
		for(int j=1;j<=6;j++){
			for(int k=1;k<=6;k++){
				ret+=dp(n-3,i,j,k);
			}
		}
	}
	cout<<ret/(1.0*6*6*6);
}

모바일로 해결했기 때문에 간격이 엉망이다.

모바일 웹컴파일러는 ideone을 이용하였다.

---

어떻게 보면 쉬운데, 어떻게 보면 확률론 때문에 조금 생각하지 못할 만한 문제라 생각한다.