프로그래머스_level3_멀리뛰기

문제:

1칸 또는 2칸 뛸수 있는 경우, 주어진 n을 뛸때 몇가지 방법을 뛸수 있는지 묻는 문제

간단한 dp문제 입니다.

피보나치 수열을 생각하면 되더군요

1칸	2칸	3칸	4칸
1	1+1	1+1+1	1+1+1+1
	2	1+2	1+1+2
		2+1	1+2+1
			2+1+1
			2+2

1, 2, 3, 5, 8, 13, 21,...

#include<iostream>
using namespace std;

int jumpCase(int n)
{
	int answer = n;
  
  int *dp = new int[answer];
	dp[1] =1;
  dp[2] =2;
  for(int i=3;i<=answer;i++){
  	dp[i] = dp[i-1]+dp[i-2];
  }
	return dp[n];
}
int main()
{
	int test = 4;

//아래는 테스트로 출력해 보기 위한 코드입니다.
	cout << jumpCase(test);
}