본문 바로가기

Problem Solving/Baekjoon OJ

[BOJ 1405] 미친 로봇

acmicpc.net/problem/1405

 

1405번: 미친 로봇

첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고,  모든 확률은 100보다 작거나 같은 자

www.acmicpc.net

당분간 글을 쓸 생각이 없었지만 예쁜 문제를 발견해 소장할 겸 가져왔다. ㅎ

 

더보기

우선 30×30 크기의 배열을 만들고, (15,15)에서 출발한다고 생각하자. 이제 간단한 재귀함수 느낌의 백트래킹을 해주면 답을 구할 수 있다. (X, Y)에서 K번 이동했을 때의 기댓값은 (X, Y-1), (X, Y+1), (X-1, Y), (X+1, Y)에서 K-1번 이동했을 때의 기댓값에 각각의 확률을 곱한 다음 전부 더해주면 된다. 이때 종료 조건은 이미 방문한 점에 방문했을 때나, 이동 횟수를 소진했을 때로 잡을 수 있다. 기댓값을 재귀적으로 구하는 과정에서 오차가 커질 것을 예상했지만, 다행히 double형을 사용하는 것만으로 맞을 수 있었다.

 

더보기
#include<bits/stdc++.h>
using namespace std;
int n,dx[4]={0,0,1,-1},dy[4]={-1,1,0,0};
double p[4];
bool v[33][33];
double dfs(int x,int y,int k)
{
    if(v[x][y]) return 0;
    if(!k) return 1;
    v[x][y]=true;
    double res=0;
    for(int i=0;i<4;i++) res+=p[i]*dfs(x+dx[i],y+dy[i],k-1);
    v[x][y]=false;
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<4;i++){
        scanf("%lf",&p[i]);
        p[i]/=100;
    }
    printf("%.10f",dfs(15,15,n));
}

'Problem Solving > Baekjoon OJ' 카테고리의 다른 글

물다이아 희자  (4) 2021.02.23
(의미 없는) Platinum I 달성  (0) 2021.02.07
[BOJ 2904] 수학은 너무 쉬워  (0) 2021.01.27
Ruby V 해결 & Platinum II 달성  (0) 2021.01.22
Platinum III 달성!  (2) 2021.01.21
[BOJ 1405] 미친 로봇  (0) 2021.01.12