[Algorithm/C] AOJ. 달팽이

문제

깊이가 n 미터인 우물의 맨 밑바닥에 달팽이가 있습니다. 이 달팽이는 우물의 맨 위까지 기어올라가고 싶어하는데, 달팽이의 움직임은 그 날의 날씨에 좌우됩니다. 만약 비가 내리면 달팽이는 하루에 2미터를 기어올라갈 수 있지만, 날이 맑으면 1미터밖에 올라가지 못합니다.

여름 장마가 찾아와, 앞으로 m 일간 각 날짜에 비가 올 확률이 정확히 75%일 전망입니다. m 일 안에 달팽이가 우물 끝까지 올라갈 확률을 계산하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 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

 

출처: <https://algospot.com/judge/problem/read/SNAIL> 

접근 방법 : 이항정리를 이용하기 위해 combination을 구하는 함수를 만들어 줬다. 그리고 여사건을 이용해 문제를 해결하기 위해 비가 오지 않을 확률을 구하는 함수 또한 만들어 줬다. 알고스팟 홈페이지의 컴파일러에서는 런타임 오류가 뜨지만 VS2017로는 매우 잘 돌아간다.

/*

Problem : 달팽이

Writer : J. I. Mun

Date : 20180115

Reference : http://jaeonysos.tistory.com

*/

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#include <math.h>

double probOfNoRain(int n,int m); //비 안올확률.

int combination(int a, int b); //a Combination b 를 출력.

int main(int argc, char * argv[]) {

int t;

int depth, period;

scanf("%d", &t);

while (t--) {

scanf("%d %d", &depth, &period);

printf("%.10f\n", (double)1-probOfNoRain(depth - period, period));

}

return 0;

}

double probOfNoRain(int n, int m) { // n = depth - period, m = period

double ret = 0;

double rain = 0.75;

double noRain = 0.25;

for (int i = 0; i < n; i++) {

ret += (double)combination(m, i)*pow(noRain, m-(double)i)*pow(rain,(double)i); 

}

return ret;

}

// 두 자연수를 입력받아 aCb 출력

// aCb = a(a-1)...(a-b+1) / b! = b(b-1)...1

int combination(int a, int b) {

int i, j, n = 1, r = 1;

for (i = a; i >= a - b + 1; i--) {

n = n * i;

}

for (j = b; j >= 1; j--) {

r = r * j;

}

return (n / r);

}