BOJ 1405 - 미친 로봇

https://www.acmicpc.net/problem/1405

1405번: 미친 로봇

아.. 이문제

풀이는 쉽지만 setprecision을 사용하는 경우에 대해서 배운 문제다

 

#include <iostream>
using namespace std;
const int dy[4]{ 0,0,1,-1 };
const int dx[4]{ 1,-1,0,0 };

int n;
long double per[4];
bool visited[30][30];

long double rst = 0;
void dfs(int cy, int cx, int cnt, long double temp) {
	if (cnt == n) {
		rst += temp;
		return;
	}
	for (int i = 0; i < 4; i++) {
		int ny = cy + dy[i], nx = cx + dx[i];
		if (!visited[ny][nx]){
			visited[ny][nx] = true;
			dfs(ny, nx, cnt + 1, temp * per[i]);
			visited[ny][nx] = false;
		}
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < 4; i++) {
		long double input; cin >> input;
		per[i] = input / 100;
	}

	visited[15][15] = true;
	dfs(15, 15, 0, 1);
	cout.precision(11); //이거 안넣어줘서 5번 틀림..
    cout << rst << '\n';
}

 

한 방향으로 최대 14번 움직이니까 r=30 c=30배열의 (15,15)좌표에서부터 dfs+백트래킹 해주면서 확률을 곱하고 더하고 하였다.