글 읽기 - 어디서 틀린지 모르겠습니다...ㅠㅠ

dhwhc0711 3년 전 0

제대로 동작하는 것 같은데 제출하자마자 바로 틀렸습니다 받았습니다...

어디서 문제가 있는지 알 수 있을까요? 감사합니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int M;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int max_num = -1;
    cin >> M;
    vector<long long> dp(1000001, 0);
    vector<int> answer(M, 0);
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;

    for (int i = 0; i < M; i++)
    {
        int n = 0;
        cin >> n;
        answer[i] = n;
        max_num = max(max_num, n);
    }

    for (int j = 4; j <= max_num; j++)
    {
        dp[j] = (dp[j - 3] % 1000000009) + (dp[j - 2] % 1000000009) + (dp[j - 1] % 1000000009);
    }

    for (int i = 0; i < answer.size(); i++)
    {
        cout << dp[answer[i]] << "\n";
    }
    
}

1207koo 3년 전 1

31번째 줄이 문제입니다.

예를 들어서 dp[j-3]=dp[j-2]=dp[j-1]=1000000008이면 계산 결과가 3000000024가 되어서 overflow가 납니다.

물론 정확히 저런 경우가 있진 않을 것 같지만 비슷한 상황이 생길겁니다.

dhwhc0711 3년 전 0

@1207koo

정말 감사합니다.. 정확하십니다 ㅠㅠ

시간 내주셔서 감사합니다

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

문제

문제

출처

ICPC

어디서 틀린지 모르겠습니다...ㅠㅠ

dhwhc0711 3년 전 0

1207koo 3년 전 1

dhwhc0711 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말