[BOJ] 미친 로봇 - Compy's Blog

미친 로봇 #

TimeLimit	MemoryLimit	Condition	TAG
1s	128MB	(1 ≤ N ≤ 14)	Implementation, Backtracking

문제는 그냥 재미있었다.. ㅋㅋㅌㅎㅌㅋ

일단 우리가 중요하게 생각할 것은 무엇보다도 오차를 줄이는 것.. 컴퓨터는 기본적으로 소수를 표현할 때 무한 소수나 엄청긴 숫자에 대해서 당연히 오차가 발생하는데 이런 것들을 어떻게 최대한 줄일까? 이런 아이디어만 있으면 쉽게 풀 수 있다.

나는 곱하기로 처리하다가 마지막에만 나눠서 처리하는 방식을 사용했다.

다행히 문제의 최대값 100^14 값이 1e28인데 double로 찍어보니 나와서 double로 맘편히 처리했다.

이번에 cout의 출력 형식 맞추는 것도 새롭게 알아간다

정답 코드


#include <iostream>
#include <queue>
using namespace std;


double probability[4];
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int n;
bool visited[50][50];

double solution(int depth, pair<int, int> pos, double current){
    if(depth >= n) return current;
    
    double local_result = 0;
    
    for(int i = 0; i < 4; i++){
        int ny = dy[i] + pos.first;
        int nx = dx[i] + pos.second;
        
        if(visited[ny][nx] || probability[i] == 0) continue;
        visited[ny][nx] = true;
        
        local_result += solution(depth+1, {ny, nx}, current*probability[i]);
//        cout << "local : " << local_result << "\n";
        visited[ny][nx] = false;
    }
    
    return local_result;
}



int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    // result = 1e28;
    cin >> n;
    for(int i = 0; i < 4; i++) cin >> probability[i];
    
    pair<int, int> start = {25, 25};
    
    
    
    double d = 1;
    int i = n;
    while(i --> 0) d*=100;
    visited[25][25] = true;
    double result = solution(0, start, 1);
    cout.precision(10);
    cout << (double)(result / d);
    
    
    return 0;
}

미친 로봇#

미친 로봇 #