Sandor의 개발 일지

Make real your dreams

1 분 소요

Question

Q

Solution

n을 1 부터 대입해서 나오는 경우의 수를 살펴보았다.
그렇게해서 확인한 식이 f(n) = f(n-1) + f(n-2) 로 피보나치 수열과 동일하였다.

  • 마지막에 한 칸 점프로 도달 할 수 있는 경우는 (n-1) + 1 이고,
    두칸 점프로 도달 할 수 있는 경우는 (n-2) + 2 이다.
    따라서 점화식 f(n) = f(n-1) + f(n-2)가 될 수 있다.

Cord

#include <string>
#include <vector>

using namespace std;

int dp[2001];

int cases(int n)
{
    if (n == 1) { return 1; }
    else if (n == 2) { return 2; }
    
    if (dp[n] != 0) { return dp[n]; }
    
    return dp[n] = (cases(n-1) + cases(n-2)) % 1234567;
}

long long solution(int n) 
{
    long long answer = 0;
    answer = cases(n);
    
    return answer;
}

/*
1, 1, 1
2, 2, 11 2 
3, 3, 111 12 21
4, 5, 1111 112 121 211 22
5, 8, 11111 1112 1121 1211 2111 122 212 221
6, 13, 111111 11112 11121 11211 12111 21111 1122 1212 2112 1221 2121 2211 222
7, 21, 1111111 111112 111121 111211 112111 121111 211111 11122 11212 12112 21112 11221 12121 21121 12211 21211 22111 1222
2122 2212 2221

f(1) = 1
f(2) = 2

n > 2
f(n) = f(n-1) + f(n-2)
*/

Result

Result

참고