글 읽기 - 안되는 텟케이스나 틀린이유좀 아르쳐주세요 ㅠㅠㅠㅠ

kdhsong 8년 전 0

안되는 텟케이스나 틀린이유좀 아르쳐주세요 ㅠㅠㅠㅠ

#include <stdio.h>
int n,i;
float value[4];
float cache[15][40][40];
bool visit[40][40];
 
bool Visit(int a,int b){
    if(!visit[a][b]){
        visit[a][b] = true;
        return false;
    }
    return true;
}
 
float dp(int a,int b,int cnt,float s){
    if(cnt == 0)    return s;
 
    float &ret = cache[cnt][a][b];
    if(ret != 0)    return ret;
     
    if(!Visit(a+1,b)){
        ret += dp(a+1,b,cnt-1,s*value[2]);
        visit[a+1][b] = false;
    }
    if(!Visit(a,b+1)){
        ret += dp(a,b+1,cnt-1,s*value[0]);
        visit[a][b+1] = false;
    }
    if(!Visit(a-1,b)){
        ret += dp(a-1,b,cnt-1,s*value[3]);
        visit[a-1][b] = false;
    }
    if(!Visit(a,b-1)){
        ret += dp(a,b-1,cnt-1,s*value[1]);
        visit[a][b-1] = false;
    }
    return ret;
}
 
int main(){
    scanf("%d",&n);
    for(i = 0; i < 4; i++){
        scanf("%f",&value[i]);
        value[i] = value[i]/100;
    }
    visit[20][20] = true;
    printf("%.10f",dp(20,20,n,1));
}

yukariko 8년 전 0

일단 소수점 10자리까지 출력해야하니 float이 아닌 double로 처리하시고

이 문제는 dp문제가 아니고 완전탐색이기 때문에 dp 관련 과정을 제거해주면 답이 나올것입니다.

kdhsong 8년 전 0

윽..그러네요 ..ㅠ yukariko님 감사합니다~~

kdhsong 8년 전 0

한가지궁금한게있는데 14정도면 완전탐색으로 다돌려도 되나요 ? 시간초과들거같아서 생각을안했었는데 ㅠ

그리고 float은 소수점 몇째짜리까지 가능하나여?ㅠ

yukariko 8년 전 0

소수점오차라는게 결국은 아래 자리에서 잘못 계산되면 반올림하면서 계속 오차가 남을 수 있기때문에 몇째자리까지라고 정해진건 없을겁니다.

그래서 저는 float는 안쓰는게 좋다고 생각합니다.

4방향에 대해 탐색을 14회니까 2^28 이라 볼 수 있는데 이 경우엔 한번 방문했던 좌표를 다시 방문하지 않기때문에

시간내에 풀리게 됩니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

안되는 텟케이스나 틀린이유좀 아르쳐주세요 ㅠㅠㅠㅠ

kdhsong 8년 전 0

yukariko 8년 전 0

kdhsong 8년 전 0

kdhsong 8년 전 0

yukariko 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말