NUMB3RS(두니발박사의탈옥)

(출처) https://algospot.com/judge/problem/read/NUMB3RS

이번에도 결국 부분문제 만들기

지금까지 풀었던 다른 DP 문제들과 전혀 다를 바 없는 문제였다. 특정 상황에서 발생할 수 있는 모든 경우를 나눠서 각각을 재귀로 해결한 뒤 다시 합쳐준다. 이번에는 원하는 답이 확률이라는 것만 살짝 다를 뿐이었다.

cache[마을][days] == days 만큼 지났을 때 해당 마을에 두니발 박사가 숨어있을 확률
cache[마을][days] += (cache[마을과 연결된 다른 마을들][days - 1] / 다른마을의 갈림길 개수)

특별한 점은 기저사례가 따로 존재하지 않고 대신 함수를 돌리기 전 미리 days가 1일일 때의 확률을 cache에 저장해놓고 시작함. 어찌 보면 days가 1이 될 때가 바로 기저사례.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

double cache[51][101];
int n;

void prep(vector<vector<int>> &town, int p) {
	// town의 각 마지막 인자에 타운이 갈 수 있는 갈림길 개수를 미리 세서 삽입
	for (int i = 0; i < town.size(); i++) {
		int temp = 0;
		for (int j = 0; j < town.size(); j++) {
			if (town[i][j] == 1) temp++;
			if (j == town.size() - 1) town[i].push_back(temp);
		}
	}
	// days가 1일 때 cache 값을 미리 초기화
	for (int i = 0; i < town.size(); i++) {
		if (town[p][i] == 1) cache[i][1] = (double)1 / town[p].back();
		else cache[i][1] = 0;
	}
}

double numb3rs(int target,int days, vector<vector<int>> &town) {
	double& ret = cache[target][days];
	if (ret != -1) return ret;

	ret = 0;
	for (int other_town = 0; other_town < town.size(); other_town++) {
		if (town[target][other_town] == 0) continue;
		
		ret += numb3rs(other_town, days - 1, town) *  (1 / (double) town[other_town].back());
	}
	
	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int testcase;
	cin >> testcase;
	while (testcase--) {
		int d, p;
		cin >> n >> d >> p;
		vector<vector<int>> town(n);
		int temp;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin >> temp;
				town[i].push_back(temp);
			}
		}

		int t;
		cin >> t;
		vector<int> q;
		
		for (int i = 0; i < t; i++) {
			cin >> temp;
			q.push_back(temp);
		}

		fill_n(cache[0], 5151, -1);
		prep(town, p);
		cout.precision(10);
		for (int i = 0; i < q.size(); i++) {
			double ret = numb3rs(q[i], d, town);
			if (i == q.size() - 1) {
				cout << ret << "\n";
				break;
			}
			cout << ret << " ";
		}
	}
	return 0;
}

기억하고 싶은 점

없음. 이전의 푼 문제들과 너무 동일한 패턴의 연속이라 별다른 메모는 생략.