예제: 장마가 찾아왔다(ID:SNAIL)

문제

깊이가 n 미터인 우물의 맨 밑바닥에 달팽이가 있습니다. 이 달팽이는 우물의 맨 위까지 기어올라가고 싶어하는데, 달팽이의 움직임은 그 날의 날씨에 좌우됩니다. 만약 비가 내리면 달팽이는 하루에 2미터를 기어올라갈 수 있지만, 날이 맑으면 1미터밖에 올라가지 못합니다.
여름 장마가 찾아와, 앞으로 m 일간 각 날짜에 비가 올 확률이 정확히 75%일 전망입니다. m 일 안에 달팽이가 우물 끝까지 올라갈 확률을 계산하는 프로그램을 작성하세요.

정정: 이 문제의 내용은 알고리즘 문제해결 전략 8.11에 나온 문제 설명과 약간 다릅니다. 책과 반대로 여기에서는 비가 내릴 경우 2미터, 맑을 경우 1미터를 올라가게 됩니다. 신고해주신 조성현님께 감사드립니다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C(1≤C≤50) 가 주어집니다. 그 후 각 줄에 우물의 깊이 n(1≤n≤1000)과 장마 기간의 길이 m(1≤m≤1000) 이 주어집니다.

출력

각 테스트 케이스마다 한 줄에 m일 안에 달팽이가 우물을 탈출할 수 있을 확률을 출력합니다. $10^{−7}$ 이하의 상대/절대 오차가 있는 답은 정답으로 인정됩니다.

예제 입력

4
5 4
5 3
4 2
3 2

예제 출력

0.9960937500
0.8437500000
0.5625000000
0.9375000000

First Thoughts

비슷한 문제

앞선 예제 "우물을 기어오르는 달팽이"의 해제 코드를 조금만 응요하면 될 거 같다. "우물을 기어오르는 달팽이"는 경우의 수를 계산하는 문제인 반면 "장마가 찾아왔다"는 확률을 계산하는 문제로 자료형과 식을 변환하여 사용해보자.

My Code

#include <iostream>
#include <cstring>
#include <iomanip>
using namespace std;
int n, m;
const int MAX_N = 1001;
double cache[MAX_N][MAX_N];
double climb2(int days, int climbed) {
	if (days == m)
		return climbed >= n ? 1 : 0;
	double& ret = cache[days][climbed];
	if (ret != -1)
		return ret;
	else
		return ret = 0.75 * climb2(days + 1, climbed + 2) + 0.25 * climb2(days + 1, climbed + 1);
}
int main() {
	int C;
	int i;
	cin >> C;
	for (i = 0; i < C; i++) {
		cin >> n >> m;//n미터 m일
		for (int j = 0; j < MAX_N; j++) {
			for (int k = 0; k < MAX_N; k++) {
				cache[j][k] = -1;
			}
		}
		cout << fixed<<setprecision(10)<<climb2(0, 0) << endl;
	}
}

Answer Code

No answer code

Difference & Faults

cache의 초기화

cache를 원래 초기화하던 방식대로 memset(cache,-1,sizeof(cache))을 이용하니 -nan이라는 이상한 문구가 떴다. 그래서 0.0으로 초기화하니 예시답은 나오는데 시간초과가 떴다. 그 이유에 대해 생각해보니 0.0이라고 초기화를 하면 입력되는 확률 중에서도 0.0으로 인식되는 것이 있어 무한반복을 돌아 시간초과가 뜨는듯 하였다. 그래서 memset이 아닌 이중 for문을 사용하여 -1로 초기화해주는 작업을 하였다. 여기서도 행은 n,열은 m으로 범위를 정할려고 했는데 생각해보니 n과 m을 초과하는 경우도 발생하여 그냥 최대 수인 1001을 모두 초기화해주었다.

Impressions

fixed와 setprecision의 사용

codeup에서 매우 자주 사용하던 함수들이다. codeup에 있는 기초문제를 풀 때만 해도 '이게 도움이 될까?','이게 정말 사용될까?' 했던 함수들이 꽤 있었는데 fixed와 setprecision 역시 그 중 하나였다. 근데 답에서 오차율을 $10^{-7}$ 이하의 상대오차가 써있는것을 보고 바로 "사용해야겠다!" 라고 생각했다.

Summary

앞에 예제에서 우물을 기어오르는 달팽이라고 매우 비슷한 경우의 수 문제를 풀어봤기 때문에 비교적 쉬운 문제였다. 조금 까다로웠다면 까다로웠을 부분은 double형의 배열을 초기화하는것, 그리고 오차율을 최대한 줄이기 위해 외부 라이브러리를 이용하는 것이다. 하지만 외부 라이브러리를 이용하는 부분은 이미 사용해본 경험이 있어 편안하게 사용할 수 있었다. 이 문제를 풀면서 느낀 것은 "모든 경험은 의미가 있다"이다. 앞으로 얼마 남지 않은 기초 100제도 완주할 수 있으면 좋겠다.