글 읽기 - 반례 부탁드립니다

pkc4913 5년 전 0

간단한 DP문제 같아서 풀었는데 잘 안되네요

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

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <queue>
using namespace std;

int dp[100001][4];
const int mod = 1000000009;
int main()
{
	int t; cin >> t;
	dp[1][1] = 1;
	dp[2][2] = 1;
	dp[3][1] = 1; dp[3][2] = 1; dp[3][3] = 1;
	for (int i = 4; i <= 100000; i++) {
		dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % mod;
		dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % mod;
		dp[i][3] = (dp[i - 3][2] + dp[i - 3][1]) % mod;
	}
	while (t--) {
		int n; cin >> n;
		printf("%lld\n", ((long long)(dp[n][1] + dp[n][2] + dp[n][3])% mod));
	}
}

luniro 5년 전 7

입력:
1
99991

출력:
-42247586

정답:
252719674

luniro 5년 전 9

3개를 더하면 int범위를 초과할 수 있어서 먼저 long long으로 변환한 후 더하셔야합니다

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

문제

문제

출처

ICPC

반례 부탁드립니다

pkc4913 5년 전 0

luniro 5년 전 7

luniro 5년 전 9

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말