[동적계획법] 10.달팽이

우물을 기어오르는 달팽이(예제)를 응용한 '장마가 찾아왔다'

https://algospot.com/judge/problem/read/SNAIL

algospot.com :: SNAIL

책과 홈페이지에 나온 문제가 약간 다르다!! 책은 비오면 1m올라가는데 홈페이지엔 2m올라간다고 되어있음

이것때문에 계속 틀리고 있었다. ㅂㄷㅂㄷ..

 

 

컨셉

 

달팽이가 올라가서 도착할 수 있는 확률을 점화식으로 나타냈다.

climb(days, climbed) // 달팽이가 days만큼 climb미터를 올라갈 수 있는 확률

 

 

 

초안

내가 쓴 답(오답, 56ms) ; 오차범위 조심

 

/**
 * @name    8.12.장마가 찾아왔다.
 * @ID      SNAIL
 * @date    2019-08-12
 * @author  Sunmon
 */
 
#include <iostream>
#include <cstring>
#include <algorithm>    // std::fill()
 
using namespace std;
double cache[1000+1][1000+1];   //climb[days][climbed]저장
int DAYS, DEPTH;   //목표 DEPTH미터 DAYS일
 
//days날에 climbed미터만큼 남았을 때, m일에 n미터 이상 올라갈 확률
double climb(int days, int climbed)
{
    if(days <= 0 ) return climbed <= 0;
    double& ret = cache[days][climbed];
    if(ret != -1) return ret;
 
    //비가 오면 2미터, 안 오면 1미터 올라감.
    //비 올 확률 75%, 안 올 확률 25%
    return ret = climb(days-1, climbed-1) /4 + climb(days-1, climbed-2) * 3 / 4;
}
 
 
int main()
{
    int C;
    cin >> C;
 
    while(C--)
    {
        cin >> DEPTH >> DAYS ;
        // memset(cache, sizeof(cache), -1);   //qNAN Error !!
        fill_n(cache[0], 1001 * 1001, -1);
        cout << climb(DAYS, DEPTH) << endl;
    }
    return 0;
}
 
 
 
 

 

 

재안

내가 쓴 답(정답, 60ms)

소수점 아래 10자리까지 표현하게 했더니 맞았다. ㅂㄷㅂㄷ

오차 범위 조심하자. 소수점 몇째자리까지 나타내느냐에 따라 달라진다.

 

 

/**
 * @name    8.12.장마가 찾아왔다.
 * @ID      SNAIL
 * @date    2019-08-12
 * @author  Sunmon
 */
 
#include <iostream>
#include <cstring>
#include <algorithm>    // std::fill()
#include <iomanip>      // setprecision()
 
using namespace std;
double cache[1000+1][1000+1];   //climb[days][climbed]저장
int DAYS, DEPTH;   //목표 DEPTH미터 DAYS일
 
//days날에 climbed미터만큼 남았을 때, m일에 n미터 이상 올라갈 확률
double climb(int days, int climbed)
{
    if(days <= 0 ) return climbed <= 0;
    double& ret = cache[days][climbed];
    if(ret != -1) return ret;
 
    //비가 오면 2미터, 안 오면 1미터 올라감.
    //비 올 확률 75%, 안 올 확률 25%
    return ret = climb(days-1, climbed-1) /4 + climb(days-1, climbed-2) * 3 / 4;
}
 
 
int main()
{
    int C;
    cin >> C;
 
    while(C--)
    {
        cin >> DEPTH >> DAYS ;
        // memset(cache, sizeof(cache), -1);   //qNAN Error !!
        fill_n(cache[0], 1001 * 1001, -1);
 
        //소수점 10자리까지 표현
        // cout << fixed;
        // cout.precision(10);
        // cout <<  climb(DAYS, DEPTH) << endl;
 
        //소수점 10자리까지 표현 2
        cout << fixed << setprecision(10) <<  climb(DAYS, DEPTH) << endl;
    }
    return 0;
}
 
 
 
 

 

 

 

주의

 

* -1.#QNAN 에러::

double형 배열을 memset을 이용하여 초기화 했을 때 발생.

 

1 2

double cache[1000][1000]; memset(cache, -1, sizeof(cache));    //-1.#QNQN error 발생!!

cs

 

NAN은 알다시피 "Not A Number"의 줄임말이다. 숫자가 아닌데 숫자 연산을 하면 나타나는 에러다. 실수형(double, float)연산을 할 때 종종 나타난다. 부동소수점으로 표현 할 수 없는 경우에도 나온다 (ex: 0/0, √-1))

이 NAN은 quiet NaNs와 signaling NaNs의 두 가지 종류가 있는데, 지금 상황에선 Quiet Nans에러가 걸린 것.

qNaN(조용한 NaN)은 유효하지 않은 값이나 연산자로 계산을 했을 때 나오는 에러다. 반대로 sNaN은 몰라 파파고 돌려봐도 모르겠다. 직접 링크로 가서 읽어볼 것.

 

아무튼 이 에러가 나타난 원인은 이거다:: double형을 memset으로 초기화 한 것.

`memset(n)`은 입력한 주소의 처음 n바이트를 c로 초기화한다. (The memset() function fills the first n bytes of the memory area pointed to by s with the constant byte c.) 그런데 double형은 실수형이라서 숫자 표현 방식이 정수와 다르기 때문에 memset을 쓰면 이상하게 표현이 될 수 밖에 없다.

애초에 정수형을 쓸 때도 왜 memset(0)혹은 memset(-1)로만 가능했는 지 생각해보자.

정수형 : (int 4바이트를 0으로 채운다) 0000 → (값) 0 / (int 4바이트를 -1로 채운다)1111 → (값) -1

이렇게 표현이 되었기 때문에 memset을 쓰던 건데, 실수형은 값을 저장하는 방식이 달라서 1111을 채운다고 해서 -1이 저장되지 않는다.

 

해결법:

 

1. array가 아닌 vector를 이용해서 값을 초기화한다.

2. for문을 돌린다.

3. stl::fill() or fill_n()을 사용한다   //fill(v.begin(), v.end(), const), #include <algorithm>

 

세번째 방법을 사용하는게 지금 memset쓰는 거랑 비슷하다.

주의할건 fill함수 안에 sizeof를 넣으면 안 된다는 거다. 왜인지는 모르겠는데, 아무튼 오류가 난다.

 

fill(): fill(v.begin(), v.end(), 숫자)인데, 2차 배열에서는 end를 구해주기 귀찮더라. 그냥 fill_n쓰는게 편하다.

fill_n(v.begin(), 연속해서 채울 범위, 채울 숫자) 이렇게 쓴다. 단, 채울 범위에는 맨 처음 begin도 포함이다.

 

이를 이용해서, 아까 memset으로 오류나던 걸 다음과 같이 바꿔줬다.

double cache[1000+1][1000+1];
fill_n(cache[0], 1001* 1001, -1);

 

 

* 소수점 나타내기 ::

//소수점 10자리까지 표현
cout << fixed;
cout.precision(10);
cout <<  climb(DAYS, DEPTH) << endl;
 
 
//소수점 10자리까지 표현 2
#include <iomanip>        // setprecision()을 포함하는 헤더
cout << fixed << setprecision(10) <<  climb(DAYS, DEPTH) << endl;

 

 

 

 

 

참고

 

fill_n(): http://www.cplusplus.com/reference/algorithm/fill_n/

fill_n - C++ Reference

 

NaN 참고

- Nan: https://en.m.wikipedia.org/wiki/NaN

NaN - Wikipedia

- qNan: http://mathworld.wolfram.com/QuietNaN.html

- sNaN: http://mathworld.wolfram.com/SignalingNaN.html

 

Signaling NaN -- from Wolfram MathWorld

http://mathworld.wolfram.com/QuietNaN.html

 

 

 

https://stackoverflow.com/questions/27581320/using-memset-in-double-type-array

using memset() in double type array