DP, 수학공식(백준 알고리즘 1892번)

♠ 문제 이해

 

이 문제는 가위바위보의 승리 확률을 구하는 문제이다. 동주와 항승이가 n번 가위바위보를 할 수 있는데, n번까지 가는 동안 k번 먼저 이기는 사람이 승리한다. n이 항상 k보다 크거나 같기 때문에 n번을 하기 전에 승부가 날 수도 있다. 

 

♠ 각 경우의 수 구하기

 

예를 들어 N = 3, K = 2 일 때 항승이가 승리할 수 있는 경우의 수는 다음과 같다. 

[이, 이]
[이, 비, 이]
[비, 이, 이]
[이, 지, 이]
[지, 이, 이]

 

위의 경우의 수를 살펴보면 [이, 이] 는 N=2, K=2 인 경우에도 나올 수 있는 경우이다. 즉 현재 N번(3번) 가위바위보를 하는 경우의 수만이 아니라 그 전의 N-1번(2번)에서 K번 이기는 경우까지 고려해야 하는 것이다. 점화식으로 나타내면 이렇게 될 것이다. 

 

DP[N, K] = DP[N-1, K] + N번까지 해서 판가름 나는 경우의 수

 

이제 여기서 N번까지 해서 판가름 나는 경우의 수를 어떻게 구할지 살펴보자. N번까지 가서 이기기 위해서는 항승이가 N-1번까지 K-1 번을 이겨야 한다. 그리고 나서 마지막 N번에 이겨서 승리하는 것이다. 이를 식으로 만들면 아래와 같다. 

 

N-1 까지 가는데 K-1 번을 이겨야 하므로 N-1 에서 K-1 만큼을 고르는 순열을 사용한다. N-1 에서 K-1 만큼 고르고 나면 N-1 -(K-1) = N-K 이므로 남은 N-K 번은 지든 비기든 상관이 없다. 다만 이기면 안된다. K-1번보다 더 많이 이기면 N번까지 가기 전에 승부가 나버리기 때문이다. 질 수도 있고 비길 수도 있으므로 경우의 수는 2가지인데, 남은 횟수가 N-K 이므로 2에 N-K 제곱을 한 만큼 경우의 수가 나온다. 

 

위에서 예를 들었던 N=3, K=2 라면 계산이 아래와 같다.

 

그런데 문제가 있다. N이 K*2와 같거나 이보다 커지면 위의 공식이 적용되지 않는다. N=4, K=2를 예로 들어보자

 

[이, 이]
[이, 비, 이]
[비, 이, 이]
[이, 지, 이]
[지, 이, 이]
[이, 비, 비, 이]
[비, 이, 비, 이]
[비, 비, 이, 이]
[이, 비, 지, 이]
[이, 지, 비, 이]
[비, 이, 지, 이]
[비, 지, 이, 이]
[지, 비, 이, 이]
[지, 이, 비, 이]

 

다섯번째 경우의 수까지는 DP[3, 2] 에 해당한다. 그리고 N번(여기서는 4번)까지 모두 써서 승리하는 경우를 살펴보자. 

앞에서 했던 것처럼 N-1 번까지의 승부에서 K-1 개를 이기는 자리로 고르고 나머지 자리를 지거나 비기는 것으로 생각하면 틀린다. 그렇게 생각하면 3번까지의 경우에서 1개를 이기는 자리로 고르고 나머지 두 자리를 지거나 비긴다는 건데, 그렇게 하면 [ 지, 지, 이, 이] 라는 경우도 생기므로 이때는 항승이가 지게 된다. 

 

즉 N-1번까지의 경우에서 K-1번 이길 뿐만 아니라 K번은 지면 안 된다는 새로운 조건이 붙는다. 

 

그렇다면 공식 중

 

위의 부분에서 N-K 번까지의 승부 중 K번 이상 지는 경우의 수는 모두 빠져야 한다. 그렇다면 K-1번 이기고 난 후 남은 N-K 번의 승부에서 K번 이상 지는 경우를 모두 구해서 2의 N-K 제곱에서 빼면 된다. 이를 식으로 나타내면

이렇게 하면 남은 N-K 번의 기회에서 K번 이상 지는 경우를 모두 구할 수 있다. 이 식을 이용하면 점화식이 이렇게 바뀐다. 

이 부분까지를  코드로 나타내면 아래와 같다. 

import sys
input = lambda: sys.stdin.readline().rstrip()
import math

n, k = map(int, input().split())

dp = [0]*(n+1)

def find(n, k):
	if k == 1:
		cnt = 1
	elif n < 2*k:
		cnt = math.comb(n-1, k-1) * 2**(n-k)
	elif n >= 2*k:
		cnt = math.comb(n-1, k-1)
		total = 0
		for i in range(k, n-k+1):
			total += math.comb(n-k, i)
		cnt = cnt*(2**(n-k)-total)
	
	return cnt

 

 

♠ 통분하여 확률을 더하고 약분하기

 

그런데 문제가 있다. 답을 구할 때, 이길 수 있는 방법의 수를 출력하는 게 아니라 항승이가 이길 확률을 출력해야 한다.

[이, 이]  => 1/9
[이, 비, 이]
[비, 이, 이]
[이, 지, 이]
[지, 이, 이]  => 4/27
[이, 비, 비, 이]
[비, 이, 비, 이]
[비, 비, 이, 이]
[이, 비, 지, 이]
[이, 지, 비, 이]
[비, 이, 지, 이]
[비, 지, 이, 이]
[지, 비, 이, 이]
[지, 이, 비, 이]  => 9/81

 

DP[4, 2] 를 구할 때 위의 경우를 참고해서 1/9 + 4/27 + 9/81 을 한 후 결과값을 약분까지 한 후 출력해야 한다는 것이다. 

1/9 에서 분모 9를 81로 맞춰주려면 분자와 분모에 모두 9를 곱해야 한다. 그런데 어차피 분모는 3**N 이므로 신경쓰지 않고, 분자만 구하면 된다. 분자 1* 3**(N-K) 를 하면 된다. 여기서는 N이 4, K는 2 이므로 1*3**(4-2) = 9 이다. 

 

이를 코드로 나타내면 아래와 같다.

for i in range(k, n+1):
	dp[i] = dp[i-1] + find(i, k)*(3**(n-i))

 

마지막으로 유클리드 호제법을 사용하여 분자와 분모를 약분한다. 

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a
    
a, b = dp[n], 3**(n)

number = gcd(a, b)
print(int(a//number), int(b//number))

 

 

♠ 전체 코드

import sys
input = lambda: sys.stdin.readline().rstrip()
import math

n, k = map(int, input().split())

dp = [0]*(n+1)

def find(n, k):
	if k == 1:
		cnt = 1
	elif n < 2*k:
		cnt = math.comb(n-1, k-1) * 2**(n-k)
	elif n >= 2*k:
		cnt = math.comb(n-1, k-1)
		total = 0
		for i in range(k, n-k+1):
			total += math.comb(n-k, i)
		cnt = cnt*(2**(n-k)-total)
	
	return cnt 
	
def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

for i in range(k, n+1):
	dp[i] = dp[i-1] + find(i, k)*(3**(n-i))

a, b = dp[n], 3**(n)

number = gcd(a, b)
print(int(a//number), int(b//number))