글 읽기 - 왜 N=100 일 때만 틀리는지 이해가 가지 않습니다.

jyb1018 4년 전 0

다른 분들의 소스코드로 돌려보면서 결과를 비교해봤는데,

정말 이해안되게도 N=100 인 단 하나의 경우에만 정답이 아닙니다.

이유가 알고 싶습니다.

#include <iostream>

using namespace std;

int cache[101][10];

int dp(int n, int start)
{
    if(start > 9 || start < 0)
        return 0;
    if(cache[n][start] != -1)
        return cache[n][start];
    
    if(n == 1 && start >= 0 && start <= 9)
        return 1;
    cache[n][start] = (dp(n-1, start-1) + dp(n-1, start+1))%1000000000;
    // if(cache[n][start] <= 0)
    //     cout << "error" << endl;
    return cache[n][start];
    
}

int main()
{
    ios_base::sync_with_stdio(false);
    fill(&cache[0][0], &cache[100][9], -1);
    int N;
    cin >> N;
    int ans = 0;
    for(int i = 1; i<10; i++)
        ans = (ans + dp(N, i)) % 1000000000;
    
    cout << ans;
}

prarie 4년 전 1

일단 문제는 fill 에 있는 것을 확인했습니다.

고치는 법은 모르겠습니다..

대안이라면, memset 을 이용하는 법이 있습니다.

memset(dp, -1, sizeof(dp)) (string.h)

또는 이중 for문을 쓰는 법이 있는데 memset 을 추천합니다..

prarie 4년 전 1

fill(&cache[0][0], &cache[100][9], -1);

fill 함수 같은 경우는 마지막 구간을 포함하지 않아서 그런 것 같네요

1. fill(&cache[0][0], &cache[100][9] + 1, -1);

2. fill(&cache[0][0], &cache[100][10], -1);

등으로 바꿔서 제출하면 AC가 뜨네요

한번 cache[100][9]를 출력해보시면 도움이 될 것 같습니다.

jyb1018 4년 전 0

@prarie 감사합니다! 배열의 end 포인터 값이 1차원과 다차원이 다르다는 사실을 처음 알았네요!

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

문제

문제

출처

ICPC

왜 N=100 일 때만 틀리는지 이해가 가지 않습니다.

jyb1018 4년 전 0

prarie 4년 전 1

prarie 4년 전 1

jyb1018 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말