[C++] 알고스팟/동적계획법 - 달팽이

문제 링크

https://algospot.com/judge/problem/read/SNAIL

algospot.com :: SNAIL

 

1. 현재날짜+1에서 한칸 더 올라가는 경우 * 0.25

2. 현재날짜+2에서 두칸 더 올라가는 경우 * 0.75

두가지 경우를 더해주면 값을 구할 수 있습니다.

 

 

구현 코드

 

	#include <iostream>
	#include <algorithm>
	#include <iomanip>
	#define endl '\n'
	#define fastio cin.sync_with_stdio(false); cin.tie(nullptr)
	using namespace std;
	const int MAX = 1001;
	int n, m;
	double cache[MAX][MAX];
	double climb(int days, int climbed){
	//m일이 지났을 때 n칸을 올라온 경우 1, 그렇지 않은 경우 0을 반환한다.
	if(days == m) return climbed >= n ? 1 : 0;
	double &ret = cache[days][climbed];
	if(ret != -1) return ret;
	return ret = 0.25 * climb(days+1, climbed+1) + 0.75 * climb(days+1, climbed+2);
	}
	int main(){
	fastio;
	int _;
	cin >> _;
	while(_--){
	fill_n(cache[0], MAX*MAX, -1);
	cin >> n >> m;
	cout << fixed;
	cout.precision(10);
	cout << climb(0,0) << endl;
	}
	return 0;
	}

view raw snail.cpp hosted with ❤ by GitHub