SNAIL 문제 책에 있는 해법으로 통과 되나요?

  • kwangswei
    kwangswei

    안녕하세요.

    SNAIL 문제 풀고 있는데요.
    이 문제 책에 있는 풀이로 정답 판정 되는지요?
    책에 있는 예제의 답은 다 제대로 나오지만,
    입력 값을 1000 500 으로 주면 정답이 나오지 않습니다. ( 시간제한 5s 로 돌렸습니다. )

    검토 부탁 드립니다~!

    #include <cstdio>
#include <cstring>
using namespace std;

int N, M;
double cache[1001][2001];

// 제가 구현한 소스.
/*
double getProbability(int n, int m )
{
    if ( m == 0 && n > 0 )
        return 0.0;

    if ( n < m )
        return 1.0;

    if ( n < 2 )
        return 1.0;

    double& ret = cache[n][m];
    if ( ret > 0.0 )
        return ret;

    ret = getProbability(n-1, m-1) * 0.25 + getProbability(n-2, m-1) * 0.75;
    return ret;    
}
*/

// 책에 있는 소스
double climb(int days, int climbed)
{
    if ( days == M )
        return climbed >= N ? 1. : 0.;

    double& ret = cache[days][climbed];
    if ( ret > 0.0 )
        return ret;

    ret = .25 * climb(days+1, climbed+1) + .75 * climb(days+1, climbed+2);
    return ret;
}

int main()
{
    int C;
    scanf("%d", &C);


    while ( C-- )
    {
        for ( int i = 0; i < 1001; i++ )
            for ( int j = 0; j < 2001; j++ )
                cache[i][j] = -1.0;

        scanf("%d %d", &N, &M);
//        printf("%.10f\n", getProbability(N, M));
        printf("%.10f\n", climb(0, 0));

    }
    return 0;
}

    11년 전
5개의 댓글이 있습니다.
  • JongMan
    JongMan

    시간 초과 나오시는 것 말씀하시는거죠? 이 문제 특성상 kwangsei님 코드보다 훨씬 빠르게 동작하는 방법이 있습니다. 힌트는 아래 있습니다 ㅎㅎ


    초기화 부분을 주목해 생각해 보세요


    11년 전 link
  • kwangswei
    kwangswei

    JongMan님 말씀하신 부분을 아예 빼버리고 입력을 1000 500 으로 해도 잘못된 답은 커녕 5초 내에 답을 내뱉지도 못하고 있습니다. 제가 잘못 짠 부분이 있는걸까요? 뭐가 문제일까요?

    초기화 부분은 memset 을 이용해서 모든 비트를 1로 초기화 하고 cache 검사하는 부분에서는 양수 여부만 체크하면 될 것 같습니다. double 의 최상위 비트는 부호비트로 1이면 음수인데, 확률은 음수는 없으니까요. 제가 생각한 것이 맞는지요?


    11년 전 link
  • JongMan
    JongMan

    음냐, 소스코드를 자세히 들여다보니 제가 예상했던 것과는 다른 이유로군요. 문제는 if ( ret > 0.0 ) 이 조건문에 있습니다.

    하는김에 쫙 스포일러 드리져;;

    이 경우 정답이 0인 경우엔 메모이제이션이 안되겠지요? 500일동안 1천미터를 올라가야 한다고 합시다. 첫날 비가 와서 1미터를 올라갔습니다. 그러면 남은 경우 모든 확률이 0인데, 499일동안 999미터를 올라가는 경우는 이제 모든 경우를 따져가며 푸는 셈이 됩니다.

    따라서 정답이 0인 경우도 고려해주셔야겠네요~

    제가 처음에 초기화 말씀드린 것은, n과 m이 같으면 답은 항상 같으니 cache를 매 입력 마다 초기화할 필요가 없다는 뜻이었습니다. ^^;


    11년 전 link
  • kwangswei
    kwangswei

    아, 그렇군요. 저도 if(ret >0.0) 에 있을 거 같아서 이걸 어떻게 하면 조금이라도 빠르게 해볼까 생각해봤는데, 사실 저 구문 자체가 느릴거라고 생각한 게 바보였네요... -_-;;;;;

    알려주신대로 한 번 해보겠습니다. 감사합니다!


    11년 전 link
  • kwangswei
    kwangswei

    말씀하신대로 if ( ret > 0.0 ) 이 문제가 맞았습니다. 0.0 이 메모이제이션이 안되서 계속 재계산 하는 문제가 맞았고 이 부분에서 초기화를 -1.0 으로 해주고 하니 통과 되었습니다. 감사합니다.


    11년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.