알고스팟 달팽이 (snail) 문제 파이썬으로 풀기

달팽이가 우물을 탈출할 확률을 구하는 문제이다.

동적계획법으로 분류가 되어있긴 하지만, 그걸 이용하지 않고 훨씬 쉬운 방법으로 풀어낼 수 있다.

 

문제를 보면, 달팽이는 비가 오는 날 2m를 기어오르고, 맑은 날은 1m를 기어오른다. (미끄러진다거나 밑으로 떨어지지 않는다!) 이 조건을 핵심으로 하여 문제를 푸는 것이다.

예를 들어, 예제 입력에 나와있는 3m를 2일안에 오를 확률을 구한다 하자. 달팽이가 미끄러지지 않기 때문에, 날이 맑던 비가오던, 달팽이는 매일 1m를 오른다. 그러므로,

3m를 2일안에 맑은 날에 1m를 오르고 비오는 날엔 2m를 오르는 달팽이가 오를 확률 = 1m를 2일안에 맑은 날에 0m를 오르고 비오는 날엔 1m를 오르는 달팽이가 오를 확률 이다.

마찬가지로 예제 입력에 있는 5m를 3일안에 맑은 날에 1m를 오르고 비오는 날엔 2m를 오르는 달팽이가 오르는 문제는 2m를 3일안에 맑은 날에 0m를 오르고 비오는 날엔 1m를 오르는 달팽이가 오를 확률을 구하는 것과 같다.

1m를 2일안에 맑은 날에 0m를 오르고 비오는 날엔 1m를 오르는 달팽이가 오를 확률은 예제 출력에 보면 0.9960937500으로 나와있다. 이를 분수로 바꾸면 15/16이다. 그리고 이 문제의 전체 경우수를 나열해보자면,

1번째 날 오른 높이	2번째 날 오른 높이
0	0
1	0
0	1
1	1

이렇게 될 것이다.

첫번째 경우(1번째날 0m, 2번째날 0m)가 일어날 확률은 1/4의 제곱이므로 1/16이다.

두번째(1,0)와 세번째(0,1) 경우 일어날 확률은 1/4*3/4=3/16이다.

네번째(1,1) 경우는 3/4*3/4=9/16이다.

 

그러면, 구해야하는 1m를 2일안에 오르는 확률은 3/16+3/16+9/16=15/16이 나온다.

이를 좀더 구체화 해보자면, 1m를 2일동안 오를 확률+1m이상을 2일동안 오를 확률이라고 할 수 있다.

1m를 2일동안 오를 경우는 0m+1m와 1m+0m 두 경우가 있고, 이것이 일어날 확률을 조합을 이용해 나타내면 (1/4)*(3/4)*2C1이 된다. 1m이상을 2일동안 오를 확률은 이 문제에선 1m+1m 한 경우 뿐이므로, (3/4)*(3/4)*2C2가 된다.

 

이를 코드로 바꾸면,

prop = 0  # 최종 확률
for i in range(height,day+1): # 최소한 비 오는 날 수=height 이어야 우물 끝까지 올라갈 수 있고, day번째까지 
    prop1 = (0.75**i)*(0.25**(day-i))  # 0.75=1m 오를 확률, 0.25=0m 오를 확률 
    prop2 = math.factorial(day)/(math.factorial(i)*math.factorial(day-i))  # 어떤 경우가 발생할 경우의 수
    prop3 = prop1*prop2
    prop += prop3
return prop

이렇게 된다.

 

전체 코드는 이렇게 된다.

#snail
import math
 
 
def snail(height, day):  # 비오면(75%) 1미터 안오면 0미터
    if height <= 0:  # height = 올라가야하는 높이 day=날 수
        return 1
    if height > day:  # 탈출이 불가능한 경우
        return 0
    prop = 0  # 확률
    for o in range(height,day+1):
        prop += (0.75**o)*(0.25**(day-o))*(math.factorial(day)/(math.factorial(o)*math.factorial(day-o)))
    return prop
 
 
case = int(input())
for i in range(case):
    n,m=map(int, input().split())  # n=높이,m=비오는날
    result = snail(n - m, m)  # 미리 빼준다
    print("%.10f"%result)

 

느낀점:

1. 오랜만에 다른 사람의 코드를 참고하지 않고 내 방법대로 풀어서 정답이 나왔다. 이런 일이 많아야 코딩이 재밌어질텐데 헣

2. 동적계획법으로 풀려면 하루마다 높이를 저장하는 방식으로 풀어야 할 거 같다. (제대로 생각하고 나온것이 아리나 대충 생각해보고 나온 생각이라 아닐 가능성 높음)