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

문제

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

코딩테스트 연습 - 멀리 뛰기

 

풀이

완전 탐색으로 풀면 시간 초과가 발생한다. 

가만 보니 2 x n 타일링 문제와 동일하다.

아래 문제에서 세로 타일 한개를 1칸, 가로타일 두 개를 2칸으로 해당 문제에 대입할 수 있다.

DP문제로 점화식을 이용해서 풀 수 있다.

2021.10.29 - [Alogirthm/Programmers] - [프로그래머스] 2 x n 타일링 (Java)

[프로그래머스] 2 x n 타일링 (Java)

 

소스코드

class Solution {    
    public long solution(int n) {
        int[] dp = new int[n+2];
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= n; i++){
            dp[i] = (dp[i-1] + dp[i-2])%1234567;
        }
        return dp[n];
    }
}