[프로그래머스] 멀리 뛰기 C++ 풀이

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

프로그래머스

 

전체 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;
int dp[2000];
long long sol(int n)
{
    if(dp[n]!=-1)
        return dp[n];
    
    if(n==0)
        return 1;
    else if(n<0)
        return 0;
    else
        return dp[n]=(sol(n-1)+sol(n-2))%1234567;
}

long long solution(int n) {
    long long answer = 0;
    fill(dp,dp+2000,-1);
    answer=(sol(n-1)+sol(n-2))%1234567;
    
    return answer;
}

 

풀이 방법

n개의 계단을 오르는 방법은 n-1개의 계단을 오르는 방법 + n-2개의 계단을 오르는 방법이다.

즉 sol(n)은 n개의 계단을 오르는 방법을 구하는것인데 이것은 sol(n-1) + sol(n-2)로 구할 수 있다.

이렇게 쭉쭉 타고 들어가다보면 n이 0이 되는데 이때 1가지의 방법이 완성된것이다.

무슨 방법? n개의 계단을 타고가는 방법.

 

dp[n]은 n개의 계단을 타는 방법을 저장해서 시간 초과를 해결한다.