8.11 경우의 수와 확률(2)_우물을 기어오르는 달팽이(Python)

문제 출처 : algospot.com :: SNAIL

algospot.com :: SNAIL

---

1. 비올 확률이 50%인 경우에 대해서 문제 분석

• 각 날마다 비가 오거나 오지 않거나 둘 중 하나이며, 가능한 m일 간 날씨의 조합은 모두 2^m가지 이다.
• 1일부터 m일까지 나타날 수 있는 모든 날씨 상황의 모든 조합의 수를 2^m으로 나누면 확률을 계산할 수 있다.
• 즉, 1일 부터 m일까지의 날씨 조합을 맑은 날은 1 비가 오면 2로 표현하여 대략 [1, 1, 1, 2, 2, ..., 1, 2] 같이 표현할 수 있다.
• 이 조합의 합이 우물의 높이인 n이상인 경우의 수를 모두 찾아 그 경우의 수를 2^m으로 나누면 된다.

 

• 모든 날씨 조합을 하나하나 만드는 완전탐색 알고리즘부터 시작한다.
• 각 날씨 조합을 m 조각으로 잘라 재귀 호출의 각 단계에서 하루 날씨가 맑을지, 비가 올지 결정한다.
• climb(C') = 지금까지 만든 날씨 조합 C'를 완성해 원소의 합이 n 이상이 되도록 하는 방법의 수
• C' : 지금까지 만든 날씨 조합으로 배열(Python에서는 리스트)형태로 매개변수를 사용한다.

 

• climb()에 대한 점화식은 다음 날부터 날이 맑은 경우와 날이 맑지 않는 경우를 모두 세기 때문에 다음과 같이 표현할 수 있다.
• climb(C') = climb(C' + [1]) + climb(C' + [2])
• C' + [x] : 배열(리스트) C'에 x을 덧붙인 결과

 

• 그러나 이런 부분 문제 정의로는 m의 크기에 따라 C'의 종류가 너무 많이 발생하기 때문에 메모이제이션을 적용할 수 없다.(정확히 이유는 모르겠지만 아마 가용 용량에 한도를 초과하는 문제인듯 하다.)
• 따라서, 선택할 정보를 최소한도로 줄이는 방법을 적용한다.
• C'에서 지금까지의 C'의 길이(지금까지 경과한 날=days)와 C'의 원소들의 합(달팽이가 지금까지 올라간 높이=climbed)를 이용하여 다음과 같이 부분 문제를 새롭게 정의할 수 있다.
• climb(days, climbed) = 지금까지 만든 날씨 조합 C'의 크기가 days이고 그 원소들의 합이 climbed일 때, C'를 완성해서 원소의 합이 n 이상이 되게 하는 방법의 수 -> 달팽이가 days일 동안 climbed미터를 기어올라 왔을 때 m일 전까지 n미터 이상 기어오를 수 있는 경우의 수

 

• 점화식은 크게 변화는 부분이 없다.
• 맨 처음의 방법과 마찬가지로 다음 날부터 날이 맑은 경우와 맑지 않은 경우를 모두 세어주는 방법을 사용한다.
• climb(days, climbed) = climb(days + 1, climbed + 1) + climb(days + 1, climbed + 2)

 

• 이렇게 부분 문제를 정의할 경우 부분 문제는 최대 n*m개이다.
• 따라서 비교적 수월하게 메모이제이션을 적용할 수 있다.

2. 코드 - 풀이 해설 방법

# m일 동안 n미터 이상 오를 확률 계산
n, m = map(int, input().split())

cache = [[-1] * (2 * n + 1) for _ in range(m)]

# 경우의 수를 반환 -> 최종적으로 2^m으로 값을 나누어야 확률을 계산 가능
def climb(days, climbed):
    # 기저 사례 : m일이 모두 지난 경우
    if days == m:
        return 1 if climbed >= n else 0

    # 메모이제이션
    if cache[days][climbed] != -1:
        return cache[days][climbed]

    # 1미터 올라간 경우 + 2미터 올라간 경우
    cache[days][climbed] = climb(days + 1, climbed + 1) + climb(days + 1, climbed + 2)
    return cache[days][climbed]

print(climb(0, 0) / 2**m)

• 주의해야 할 부분으로 이 함수는 경우의 수를 반환한다.
• 따라서 반환된 결과를 2^m으로 나누어야 문제에서 요구하는 확률을 구할 수 있다.
• cache의 크기를 m X (2*n+1)로 설정했는데 매일 2미터씩 오르는 경우가 있기 때문이다. 

---

3. 만일 비올 확률이 75%라면?

• 비올 확률이 75%로 올라간 경우라면 직접적으로 경우의 수를 구하는 것이 까다로워진다.
• 따라서 경우의 수가 아니라 직접적으로 확률을 반환해주는 함수를 사용한다.
• 다행히도 부분 문제가 바뀐 것은 아니기 때문에 비교적 쉽게 변환이 가능하다.
• climb2(days, climbed) = 달팽이가 지금까지 days일 동안 climbed미터를 기어 올라 왔을 때 m일 전까지 n미터 이상 기어올라갈 수 있을 확률

 

• 점화식은 다음과 같다.
• climb2(days, climbed) = 0.25 * climb2(days + 1, climbed + 1) + 0.75 * climb2(days + 1, climbed + 2)

4. 코드 - 풀이 해설 방법

cache2 = [[-1] * (2 * n + 1) for _ in range(m)]

# 만일 비올 확률이 75%면??
# 이 함수는 경우의 수가 아닌 확률을 직접 반환하게 된다.
def climb2(days, climbed):
    # 기저 사례 : m일이 모두 지난 경우
    if days == m:
        return 1 if climbed >= n else 0

    # 메모이제이션
    if cache2[days][climbed] != -1:
        return cache2[days][climbed]

    # 1미터 올라간 경우 + 2미터 올라간 경우
    cache2[days][climbed] = 0.25 * climb2(days + 1, climbed + 1) + 0.75 * climb2(days + 1, climbed + 2)
    return cache2[days][climbed]
    
 print(climb2(0, 0))

• 위 코드와 바뀐 점은 확률을 반환하기 때문에 출력 단계에서 따로 2^m으로 나누지 않아도 된다는 점이다.

---

github : Algorithmic_Problem_Soving_Strategies/code8_18.py at main · LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies (github.com)

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies