[프로그래머스] 멀리 뛰기

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

n번째 칸에 이동하는 방법 수는 n-1번째 칸에서 1칸 이동한 수와 n-2번째 칸에서 2칸을 한번에 이동한 수와 같다.

따라서 n번째 칸에 이동한 방법의 수를 dp[n]이라 하면 dp[n] = dp[n-1] + dp[n-2]가 성립한다.

코드

C++

#include <string>
#include <vector>

using namespace std;

long long dp[2001];

long long solve(int idx){
    if(dp[idx] != -1) return dp[idx];
    return dp[idx] = (solve(idx-1) + solve(idx-2)) % 1234567;
}

long long solution(int n) {
    long long answer = 0;
    fill(dp, dp+n+1, -1);
    dp[1] = 1;
    dp[2] = 2;
    answer = solve(n);
    return answer;
}

Java

class Solution {
    long[] dp = new long[2001];
    final int DIV = 1234567;

    public long solve(int idx) {
        if (dp[idx] != -1) return dp[idx];
        return dp[idx] = (solve(idx - 1) + solve(idx - 2)) % DIV;
    }

    public long solution(int n) {
        long answer = 0;
        for(int i=1; i<=n; i++) dp[i] = -1;
        dp[1] = 1;
        dp[2] = 2;
        answer = solve(n);
        return answer;
    }
}