1405번: 미친 로봇
첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자연수 또는 0이다. 그리고, 동서남북으로 이동할 확률을 모두 더하면 100이다.
www.acmicpc.net
이동할 때마다 그 방향에 부여된 확률을 곱해주면 그 경로로 이동하는 확률을 구할 수 있다.
다양한 경로가 있을 것이고, 각각의 경로로 이동하는 확률을 차곡차곡 더해줌으로써 전체 확률 또한 구할 수 있다.
완전 탐색을 통해 이미 방문한 좌표를 다시 방문하지 않는 경로를 모두 구해서 그 경로로 이동하는 확률을 결과값에 누적해준다면 원하는 결과를 얻을 수 있다.
|
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
bool map[29][29];
vector<double> directPer;
vector<pair<int, int>> dydx = { make_pair(1,0), make_pair(-1,0), make_pair(0,1), make_pair(0,-1) };
int moveMax;
double result = 0;
void Solution(int Y, int X, int moveCnt, double multiPercent)
{
if (moveCnt == moveMax)
{
result += multiPercent; // 퍼센트 누적
return;
}
for (int i = 0; i < 4; i++) // 동 서 남 북
{
int nextY = Y + dydx[i].first, nextX = X + dydx[i].second;
if (map[nextY][nextX]) continue;
map[nextY][nextX] = true;
Solution(nextY, nextX, moveCnt + 1, multiPercent * directPer[i]);
map[nextY][nextX] = false;
}
}
int main(void)
{
int E, W, N, S;
cin >> moveMax >> E >> W >> N >> S;
directPer.push_back(E*0.01);
directPer.push_back(W*0.01);
directPer.push_back(N*0.01);
directPer.push_back(S*0.01);
map[14][14] = true; // 중앙에서 시작
Solution(14, 14, 0, 1);
printf("%.9f", result);
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
알고리즘 200일 프로젝트 - 29day
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 4641번: Doubles (0) | 2020.05.06 |
|---|---|
| 백준 2858번: 기숙사 바닥 (0) | 2020.05.05 |
| 백준 1213번: 팰린드롬 만들기 (0) | 2020.04.30 |
| 백준 2981번: 검문 (0) | 2020.04.30 |
| 백준 1062번: 가르침 (0) | 2020.04.29 |