<종만북> 08. 동적계획법_우물을 기어오르는 달팽이 c++

확률과 경우의 수는 밀접한 관련이 있기 때문에 많은 경우 확률을 계산하는 문제에도 동적 계획법을 써먹을 수 있다.

먼저 책의 예제에서 각 날짜에 비가 올 확률이 정확히 50%라고 가정할 때, m일 안에 달팽이가 우물 끝까지 올라갈 확률을 먼저 본다.

m일 간 비가 오거나 오지 않거나 둘 중 하나이니, 날씨의 조합은 모두 2^m가지 이다. 따라서 날씨 조합 중 합이 n이상인 조합의 수를 센 뒤, 전체 조합 수인 2^m으로 나누면 된다.

climb (days, climbed)= 지금까지 만든 날씨의 조합 C의 크기가 days이고 그 원소들의 합이 climbed일 때, C를 완성해서 원소의 합이 n이상이 되게 하는 방법의 수

const int MAX_n = 1000;

int n, m;
int cache[MAX_n][2 * MAX_n + 1];

int climb(int days, int climbed) {
	if (days == m) return climbed >= n ? 1 : 0;

	int& ret = cache[days][climbed];
	if (ret != -1) return ret;

	return ret = climb(days + 1, climbed + 1) + climb(days + 1, climbed + 2);
}

1. 매일 2m씩 올라갈 수 있기 때문에 cache의 열을 2*MAX+n +1 로 한다.
2. days가 m일이 된 경우 climbed(days 때 올라간 높이)가 n보다 크면 1을 반환 (1개의 경우), 아니면 0을 반환한다.
3. 오늘 날씨가 맑은 경우와 비가 오는 경우를 모두 세기 때문에 두 경우를 더한다.

double climb2(int days, int climbed) {
	if (days == m) return climbed >= n ? 1 : 0;

	double& ret = cache[days][climbed];
	if (ret != -1) return ret;

	return ret = 0.75 * climb2(days + 1, climbed + 1) + 0.25 * (days + 1, climbed + 2);
    }


int main() {
	cin >> n >> m;

	fill_n(cache[0], MAX_n * MAX_n, -1);
	cout << fixed << setprecision(10) << climb2(0,0) << endl;

	return 0;
}

1. 앞의 코드에서 확률을 곱하는 부분만 추가했다.
2. 경우의 수가 아니라 확률을 직접 반환하기 때문에 반환형이 double
3. int 형이 아니기 때문에 memset으로 초기화 할 수 없다
   std::fill_n :parameter로 변경하려는 워소의 범위 시작 주소, 원소 갯수, 변경 값을 넣는다.
4. iomanip::setprecision : 출력 범위를 지정할 때 사용
   fixed가 없는 경우: 정수부+소수부 기준으로 반올림
   fixed가 있는 경우: 소수부를 기준으로 반올림