코드업 3704 계단오르기2

www.codeup.kr/problem.php?id=3704

계단 오르기 2

 

문제 설명    내 문제집에 추가

n개의 계단이 있다.

어떤 사람이 계단을 오르려 하는데 이 사람은 계단을 한번에 1계단 2계단 또는 3계단씩 오를 수 있다.

이 사람이 계단을 오를수 있는 경우의 수를 1000으로 나눈 나머지를 구하여라

입력

계단의 수 n이 입력된다. ( 1 <= n <= 100,000 )

출력

계단을 오를 수 있는 가지수에 1000으로 나눈 나머지를 출력한다.

입력 예시   예시 복사

5

출력 예시

13

#include <iostream>
using namespace std;

int memoz[100001];

int		recv(int n)
{
	if (memoz[n])
		return (memoz[n]);
	if (n == 1 || n == 2)
		return (n);
	if (n == 3)
		return (4);
	memoz[n]= recv(n - 3) + recv(n - 2) + recv(n - 1);
	return memoz[n];
}

int main(void)
{
	int n;
	cin >> n;

	int ret = recv(n);
	cout << ret % 1000;
}

 

이렇게 풀면 

- 총 13개 중 6번째 테스트 케이스 -
점수 = 38 / 100 입력: 50

정답

642 -----------------

출력 결과

778 =================

 

위의 케이스에서 틀림 

 

#include <iostream>
using namespace std;

int memoz[100001];

int		recv(int n)
{
	if (memoz[n])
		return (memoz[n]);
	if (n == 1 || n == 2)
		return (n);
	if (n == 3)
		return (4);
	memoz[n]= recv(n - 3) %1000 + recv(n - 2)%1000 + recv(n - 1)%1000;
	return memoz[n];
}

int main(void)
{
	int n;
	cin >> n;

	int ret = recv(n);
	cout << ret % 1000;
}

%1000 을 각각 해주니까 잘 나온다.