10844 쉬운 계단 수

 

재귀는 짰는데 메모이제이션을 으음...

 

 

2 5 _ _ _ _

 

이렇게 되어 있을 때 이전에 2번째 자리에 5가 온 경우를 구한 적이 있다면 이거 활용하면 되니깐

 

cache 배열을 이차원으로 둬서 활용하면 되지 않을까?

 

위 같은 경우라면 cache[2][5] != -1이면 이렇게

 

코드는 아래처럼 짰음 ^__^

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#define MOD 1000000000

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int cache[105][10];
int ans;

int    calc(int before, int len)
{
    if (len == 0)
        return 1;

    int& ref = cache[len][before];

    if (ref != -1)
        return ref;

    int a = 0, b = 0;
    if (before != 0)
        a = calc(before - 1, len - 1);
    if (before != 9)
        b = calc(before + 1, len - 1);

    return ref = (a + b) % MOD;
}

void    func(int len)
{
    for (int i = 1; i < 10; i++)
    {
        ans = (calc(i, len - 1) + ans) % MOD;
    }
}

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

    memset(cache, -1, sizeof(cache));

    func(n);
    cout << ans << endl;

    return 0;
}

 

---

이 문제는 여러번 틀리고 맞았다ㅠ

 

처음에 MOD를 아래처럼 사용했다

 

내 생각에는 더하고 난 결과를 MOD를 하면 오버플로우 나지 않을까??? 싶어서 더하기 전 미리 MOD 취해버리자!였는데 틀렸음ㅋㅋ

 

 

이렇게 고치니 맞았다.

 

알고보니 

 

a = 999999999

b = 999999999 라고 가정하면

 

a % MOD + b % MOD = 1999999998이 되지만

 

(a + b ) % MOD라고 하면 99999998이 되어서 오버플로우가 나지 않는다 (와우)

 

이걸 int 범위 안에 넣게 하기 위해서 마지막에 자른다고 생각하면 잘 이해된다.

 

암튼 덧셈부터 하고 MOD하는게 오버플로우가 나지 않는 이유는 결과값이 10억 미만인게 보장이 됨 (마지막에 MOD 취해버리니깐) 그래서 이 두개를 더하면 20억 미만이 돼서 당연히 int안에 들어간다!

 

> 만약 덧셈이 두 개 이상이라면?

 

((a+b) % MOD + c) % MOD

 

이런 순서대로 더한다

 

> 곱셈이라면??

 

64비트 쓰세용