글 읽기 - 쉬운계산수 top-down으로 풀때 문제점을 모르겠습니다.

minjae200 4년 전 0

bottom-up으로는 쉽게 풀렸는데 top-down으로 풀려니까 통과가 안됩니다....

제가 어느부분을 실수하고있는지 지적부탁드립니다....

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

typedef long long ll;
const int MOD = 1000000000;
const int MAX = 100 + 1;
int N;
ll cache[MAX][10];

ll solve(int n, int m)
{
    if(m > 9 || m < 1) return 0;
    if(n == 1) return 1;
    ll &ret = cache[n][m];
    if(ret != -1) return ret;
    ret = solve(n-1, m-1) % MOD + solve(n-1, m+1) % MOD;
    return ret % MOD;
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(cache, -1, sizeof(cache));
    // freopen("input.txt", "r", stdin);
    cin>>N;
    ll res = 0;
    for(int i=1; i<=9; i++){
        res = (res + solve(N, i)) % MOD;
        // cout<<solve(N,i)<<endl;
    }
    cout<<res % MOD<<'\n';
    return 0;
}

seico75 4년 전 0

위 소스에서는 N = 2일때

i = 1 이면 1, i = 9 이면 2가 나옵니다.

i = 1 이면, 10, 12 라서 2

i = 9 이면 98 이라서 1이 나와야하나...

12, 98, 9(10) 를 카운트하네요.

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

문제

문제

출처

ICPC

쉬운계산수 top-down으로 풀때 문제점을 모르겠습니다.

minjae200 4년 전 0

seico75 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말