C++ (코딩테스트) - 멀리 뛰기(프로그래머스)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12914

프로그래머스

 

피보나치로 푼 코드(정답) 완전간다...

#include <string>
#include <vector>

using namespace std;

long long solution(int n) {
vector<long long> pd(2000);
	pd[0] = 1;	pd[1] = 2;

	for (int i = 2; i < n; i++)
		pd[i] = (pd[i - 1] + pd[i - 2]) % 1234567;
	return pd[n-1];
}

 

조합으로 풀었을때 시간초과 코드

void Combination(int n, int r, int index, int depth, int& res)
{
	if (r == 0)
	{
		res++;
	}
	else if (depth == n)
	{
		return;
	}
	else
	{
		Combination(n, r - 1, index + 1, depth + 1,res);
		Combination(n, r, index, depth + 1,res);
	}
}


long long solution(int n) {
	long long answer = 0;

	int ndiv2 = n / 2;

	for (int i = 0; i <= ndiv2; i++)
	{
		int x = 0;
		Combination(n - i, i, 0, 0, x);
		answer += x;
	}
	return answer % 1234567;
}