[백준] 17367: 공교육도박 파이썬 풀이

17367번: 공교육 도박

 

풀이

• 게임의 진행
  • 주사위를 굴릴 기회가 있으면, 현재 상태에 대해 기댓값(현 상태에서 한 번더 주사위를 굴렸을 때의 기댓값)을 판단한다.
    • 판단한 기댓값이 현재 상금(현재 게임을 멈췄을 때 얻을 수 있는 상금)보다 높다면 go
    • 아니라면 멈추고 현재 상금을 받음
  • 이러한 메커니즘 때문에, 주사위를 굴릴 기회가 많을 수록 기댓값이 높아짐
• 풀이
  • d[x][i][j][k] : 굴릴 기회가 x 번 남았을 때, 주사위 눈이 i, j, k가 나왔을 때 얻을 수 있는 상금(혹은 상금의 기댓값)
  • x-1, i, j, k 는 다음 수행에서 i는 반영 되지 않고, j가 첫 번째, k가 두 번째 눈으로 반영 된다.
    • 주사위는 가장 최근에 굴린 3개만 반영.
    • ex) 총 6번의 기회가 있을 때 : 2번째 시행에서 기회가 3번 남았을 때 1, 2, 3이 나옴
    • -> 한 번 더 수행해서 4번째 시행에서 6이 나오면 기회가 2번 남고, 이러면 주사위는 2, 3, 6
  • 이러한 방법으로 이전의 상태가 현재의 상태에 영향을 미침 -> dynamic programming

(+ 알고리즘에서 확률(또는 기댓값)을 구할 때는, 모든 경우의 수를 따져서 구하는 게 일반적인 것 같다)

코드

def exp(x):
    total = 0
    for i in range(6):
        for j in range(6):
            total += sum(d[x][i][j])
    return total/216

def prize(i,j,k):
    if i == j == k:
        return 10000 + (k + 1) * 1000
    elif i == j:
        return 1000 + (j + 1) * 100
    elif i == k:
        return 1000 + (k + 1) * 100
    elif j == k:
        return 1000 + (k + 1) * 100
    else:
        return (max([i, j, k]) + 1) * 100

def sol(x):
    # 기회가  x 번 남았을 때, 주사위 눈이 순서대로 i, j, k 가 나왔을 경우
    for i in range(6):
        for j in range(6):
            for k in range(6):
                if x == 0:
                    d[x][i][j][k] = prize(i, j, k)
                else:
                    # i, j, k가 나오고 한 번 더 수행했을 때 얻을 수 있는 기댓값
                    # j, k, (1~6) 의 상금 / 6
                    e = sum(d[x - 1][j][k]) / 6

                    # 현재 상태가 한 번 더 수행했을 때 기댓값보다 높으면 멈춤
                    # 그전 점수를 그대로 가져옴
                    if d[x - 1][i][j][k] > e:
                        d[x][i][j][k] = d[x - 1][i][j][k]
                    # 기댓값이 높으면 한 번 더 수행한다고 생각
                    # 해당 기댓값을 저장
                    else:
                        d[x][i][j][k] = e


N = int(input())
d = [[[[0.0]*6 for _ in range(6)] for _ in range(6)] for _ in range(N)]
E = [0.0]*(N-2)

# 추가로 던질 기회가 x 번 남았을 때 확률 구하기
for x in range(N-2):
    sol(x)
    E[x] = exp(x)

print(E[N-3])