백준 17367번 풀이.

backjoon 17367번 풀이

문제 링크
자매품 문제 링크

• 분류 : dp

---

접근법

• 기댓값 $E(X)$에 대해서 개념이 잡혀 있어야 한다.
• 최소 3번은 굴려야 하지만 그 다음부터는 n이 허용하는 데까지 굴릴 수 있다.
• 문제 설명을 잘 이해해야 한다.

처음에 문제를 제대로 이해 못해서 헤맸다. 기댓값이 최대가 되도록 플레이한다는 의미는 현재 상황에서 stop할지 한번 더 굴려볼지의 판단 기준을 기댓값으로 정하겠다는 의미이다. 즉, 더 기댓값 $E(X)$가 큰 쪽으로 행동을 항상 결정한다.

위 공식에 따라 해당 경우의 상금*해당 경우가 일어날 확률이 된다. 해당 경우가 일어날 확률은 그 경우에 쓰인 주사위 수 = n이라 하면 $\frac{1}{6^{n}}$이 된다.

dp 정의 : dp[a][b][c][left] : 최근 고른 주사위 수 3개가 a,b,c이고 앞으로 굴릴 수 있는 횟수가 left일때 얻을 수 있는 최대 기댓값 시간 복잡도는 문제 수에 비례한다.

$time\,complexity <= 6\times6\times6\times1000 = 256000$

source code

// 일반 문제풀기용 템플릿
#include <bits/stdc++.h>
using namespace std;
double dp[7][7][7][1001];
int cal(int a, int b, int c) {
	// 상금 계산
	if (a == b && b == c)
		return 10000 + a * 1000;
	else if (a == b || b == c || c == a)
		return 1000 + (a == b ? a : c) * 100;
	else {
		int maxd = a;
		maxd = max(maxd, b);
		maxd = max(maxd, c);
		return maxd * 100;
	}
}
double solve(int a, int b, int c, int left) {
	// (a,b,c), 남은 횟수 left
	double cur = cal(a, b, c);
	// 더 주사위를 굴릴 수 없으므로 현재 최선인 현재 상금을 계산
	if (left == 0)
		return cur;
	double& ret = dp[a][b][c][left];
	// double일 경우 ret!=-1이 안먹힌다.. nan
	if (ret > 0)
		return ret;
	// 현재 기댓값 vs 더 굴리는 기댓값 비교
	double more = 0;
	for (int i = 1; i <= 6; i++)
		more += solve(b, c, i, left - 1);
	return ret = max(cur, more / 6);
}
int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	// using dp
	// dp[a,b,c,left] = 최근 던진눈 3개가 (a,b,c)이고 앞으로 던질 수 있는 횟수가 left일때
	// 받을 수 있는 상금의 기댓값
	// 모든 dp case에 대해 dp를 구하고 그걸 다 더한다음 6*6*6으로 나누면됨
	// tc : 6*6*6*1000 = 256000 = ㅆㄱㄴ
	int n;
	cin >> n;
	double sum = 0;
	memset(dp, -1, sizeof(dp));
	for (int i = 1; i <= 6; i++)
		for (int j = 1; j <= 6; j++)
			for (int k = 1; k <= 6; k++) {
				sum += solve(i, j, k, n - 3);
			}
	printf("%.8lf", sum / (6*6*6));
	return 0;
}

한 번에 맞추지 못함

• 이유?
  • double형을 사용하면 memset으로 -1을 dp배열에 채운 다음 함수 내 재활용 부분에서
    if(ret!=-1) 으로 조건을 확인하면 nan 오류가 나온다. 아무래도 실수형이다 보니 -1로 설정했다 하더라도 ret==-1이 삑사리가 나는 경우가 많은 것 같다. 이럴 때는
    범위형으로 if(ret>0)같은 code를 써야 한다.
  • 주사위가 1~6이라 아무 생각없이 dp[6][6][6][1001]로 처음에 설정했었는데 당연히 index가 0부터이므로 dp[7][7][7][1001]으로 크기를 설정했어야 했다.
  • 또 code상 제일 위 함수 cal 부분에서 상금을 계산할 때 조건문으로
    if(a==b==c)로 적어버렸다. ㅋㅋ 어이가 없더라.
  • 마지막 printf부분에서 6*6*6=216인데 256으로 갖다 박아버렸다. 왜이러냐

총평

• 오랜만에 문제를 푸니까 그 전에도 나왔던 잔실수가 강화된 기분이다.
• 풀기전 전체적인 그림을 그리고 들어가야 하는데 이 시퀀스도 전보다 오래걸림
• 머리가 잘 안돌아가는 기분