글 읽기 - c++] dp문제에서 중간에 어느 부분에서 틀린 것인지 궁굼합니다.

thyung 4년 전 0

(i-1)+1 과 (i-2)+2 와 (i-3)+3 의 경우로 나눠서 계산한 후 더해주는 방식으로 문제를 풀었습니다.

1000000009로 나눠주는 것도 각각의 경우마다 모두 해주었습니다.

코드 제출을 하니 5%에서 틀렸다고 나옵니다. 어느 부분에서는 통과하지만 통과하지 못하는 케이스가 있는 거 같습니다.

어디서 논리적으로 오류가 있는지 찾지를 못해, 질문게시판에 질문을 올리게 되었습니다.

감사합니다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

long long dp[4][100001];
//[1][i] -> (i-1)+1
//[2][i] -> (i-2)+2
//[3][i] -> (i-3)+3
int main() {
	int T;
	vector<int> vc;
	int max = 0;
	cin >> T;
	while (T--) {
		int temp;
		cin >> temp;
		vc.push_back(temp);
		max = max > temp ? max : temp;
	}
	dp[1][1] = 1;
	dp[2][2] = 1;
	dp[1][3] = 1;
	dp[2][3] = 1;
	dp[3][3] = 1;
	for (int i = 4; i <= max; i++) {
		for (int j = 1; j <= 3; j++) {
			for (int k = 1; k <= 3; k++) {
				if (j != k) {
					dp[j][i] = dp[j][i] + (dp[k][i - j] % 1000000009);
				}
			}
			dp[j][i] = dp[j][i] % 1000000009;
		}
		dp[0][i] = (((dp[1][i] + dp[2][i])%1000000009) + dp[3][i])%1000000009;
	}
	for (int i = 0; i < vc.size(); i++) {
		cout << dp[0][vc[i]] << '\n';
	}
}

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

문제

문제

출처

ICPC

c++] dp문제에서 중간에 어느 부분에서 틀린 것인지 궁굼합니다.

thyung 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말