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

홈런볼·2023년 8월 14일

프로그래머스

목록 보기

32/36

문제링크

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

문제설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

제한사항

n은 1 이상, 2000 이하인 정수입니다.

입출력

n	result
4	5
3	3

접근방법

칸이 1개일때 부터 도달할 수 있는 방법을 체크했다.
칸 = 1, 도달 방법 수 1

칸 = 2, 도달 방법 수 (1,1), (2) -> 2

칸 = 3, 도달 방법 수 (1,1,1) ,(2,1) (1,2) -> 3

칸 = 4, 도달 방법 수 문제에 언급된대로 5

칸 = 5, 도달 방법 수 (1,1,1,1,1) (1,2,1,1) (1,1,2,1) (1,1,1,2) (2,1,1,1) (2,2,1) (2,1,2) (1,2,2) -> 8

칸 = 6, 도달 방법 수 (1,1,1,1,1,1) (1,2,1,1,1) (1,1,2,1,1) (1,1,1,2,1) (1,1,1,1,2) (2,1,1,1,1) (2,2,1,1) (2,1,2,1) (2,1,1,2) (1,2,2,1) (1,1,2,2) (1,2,1,2) (2,2,2) -> 13

이므로 규칙을 발견했을 때 칸 n개를 도달하는 방법은 칸 n-1개 도달하는 방법과 칸 n-2개를 도달하는 방법을 더한 값이라는 결과를 파악했다.
다이나믹 프로그래밍과 메모제이션으로 이전의 값을 저장해 시간복잡도를 줄인다.

구하는 식

정의 : dp[n] = 칸 n개에 도달하는 방법의 수
초기값 dp[1] = 1 / dp[2] =2
구하는 답 : dp[n]
점화식 : dp[n] = (dp[n-1] + dp[n-2]) % 1234567

코드

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