글 읽기 - 무엇이 문제일까요...? ㅠ

kim031504 4년 전 0

테스트 케이스는 잘 나오는데, 그냥 틀렸다고 나옵니다... ㅠ

코드 상에서 주석으로 상세히 무엇을 의도해 놓았는지 설명했습니다!

시간 복잡도를 계산해 보아도 N으로 나오는데,

딱히 틀린 부분이 없는 것 같은데 이유를 못 찾겠습니다 ㅠㅠ

#include <iostream>

using namespace std;

int main()
{
	int N;
	cin >> N;

	// 인덱스의 편의상 N+1개 할당!
	int *D = new int[N + 1];

	// 초기의 가장 작은 문제의 자명한 부분은 그 해를 채워 넣는다.
	D[0] = 1;
	D[1] = 1;


	// 바로 답이 나오는 경우이다.
	if (N == 1)
	{
		cout << 1%10007 << endl;
	}


	// 동적 규칙을 쫓아야 하는 부분이다.
	else
	{
		// 반복문을 돌며 N까지 채워 나간다.
		for (int i = 2; i <= N; i++)
		{
			D[i] = D[i - 2] + D[i - 1];
		}

		// 최종적으로 구한 값에 10007을 나눈 나머지를 출력한다.
		cout << D[N]%10007 << endl;
	}

	return 0;
}

lim551 4년 전 0

DP 구하는 도중에 모듈로 안 하셨습니다

kim031504 4년 전 0

아! 감사합니다! 배열에 저장된 값이 기하급수적으로 커짐을 방지하기 위하여

모듈러 연산을 취한 것이로군요!

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

문제

문제

출처

ICPC

무엇이 문제일까요...? ㅠ

kim031504 4년 전 0

lim551 4년 전 0

kim031504 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말