Baekjoon 1405번 미친 로봇

문제

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

걸린 시간

01 : 13 : 40

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int n;
int arr[30][30]; // 1 : 방문
int dy[4] = {0, 0, -1, 1};
int dx[4] = {1, -1, 0, 0};
double dp[4]; // direction percent
double percent = 0;

void solve(int y, int x, int k, double p){
    // 기저 사례
    if(k == n) percent += p;
    // 재귀 호출
    for(int i = 0; i < 4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(!arr[ny+15][nx+15] && k <= n){ // 방문하지 않았으면
            arr[ny+15][nx+15] = 1;
            solve(ny, nx, k+1, p*(dp[i]/100));
            arr[ny+15][nx+15] = 0;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(auto& i : dp) cin >> i;
    memset(arr, 0, sizeof(arr));
    arr[0+15][0+15] = 1;
    solve(0, 0, 0, 1);
    cout << setprecision(10) << percent;
    return 0;
}

setprecision 함수를 이용해 소수점 이하 10번째 자리까지 출력범위를 지정해주어야 정답으로 인정된다.