[백준 | Python] #13252 - 카지노

13252번: 카지노

 

아이디어

우선 최적의 전략이 무엇인지 알아내는 것이 중요하다.

결론부터 말하면, 플레이어들이 영역에 칩을 최대한 고르게 베팅하는 것이 최적의 전략이다.

사실 이게 왜 최적의 전략인지는 잘 모르겠다. 대충 맞는 것 같아서 풀었다...

 

풀다보니 이게 골드가 맞나 싶었다.

수학으로 풀리는 건가 싶어 고민해 봐도 도저히 간단한 식으로 유도될 것 같지 않았다.

 

그러면 DP를 의심해 본다.

(N, M, K)의 게임의 확률을 P(N, M, K)라 하면 적당한 p에 대해 (0<=p<=1)

P(N-(N//M), M, K-1)*p + P(N-(N//M+1), M, K-1)*(1-p)로 계산 된다.

이렇게 재귀 DP를 굴리면 될 듯도 하다.

 

시간이 초과되지 않을까 의심됐지만 다른 방법이 안 떠올라 일단 구현을 했다.

 

구현

위 설명에 따른 재귀 DP를 구현하되, 메모이제이션을 추가하고, 작은 K나 N==0일 때를 주의하면 된다.

p = 1 - a%b/b이다.

 

코드

def f(a,b,c):
    if (a,b,c) in memo:
        return memo[(a,b,c)]
    elif a == 0:
        return 0
    elif c == 1:
        if a == 1:
            return 1 - 1/b
        else:
            return 1
    
    x = f(a - a//b, b, c-1)
    y = f(a - a//b - 1, b, c-1)
    z = (x * (b - a%b) + y * (a%b)) / b
    memo[(a,b,c)] = z
    return z

n,m,k = map(int, input().split())
memo = {}
print(f(n,m,k))

잘 돌아간다. 시간이 생각보다 남아돈다.

결과를 관찰해보니 O(K^2) 정도 되는 것 같다.

 

숏코딩

from functools import*
@cache
def f(n,k):return 0if n<1else-(n==1)/m+1if k<2else(f(n-n//m,k-1)*(m-n%m)+f(n-n//m-1,k-1)*(n%m))/m
n,m,k=map(int,input().split())
print(f(n,k))

cache 데코레이터는 강력하다.