코테 연습 with Kotlin - 5

오늘 풀어본 문제는 프로그래머스 Level 2 멀리 뛰기였다.
(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하면 됩니다.

<풀이>

1. 피보나치 수열 응용

문제를 보고 메모장에 1을 하나씩 적어가며 무슨 문제인지 이해하려 하였다. 적다보니 피보나치 수열의 형태를 띄고 있다는 것을 알게 되었고 그것을 적용하여 문제를 풀었다.

2. 조합 응용 (dp)

문제를 다 풀고 다시 한번 문제를 보니 조합의 형태가 보였다 dp를 응용하여 풀 수 있을 것 같다.
예) n의 경우 -> nC0 + n-1C1 + n-2C2+ n-3C3 ... + n/2Cn/2

class Solution {
    fun solution(n: Int): Long {
        var resultArr = Array<Long>(n+1, {0})
        resultArr[0] = 1;
        resultArr[1] = 1;
        for(i : Int in 2..n){
            resultArr[i] = ((resultArr[i-1] %1234567) + (resultArr[i-2]) %1234567) %1234567
        }
        var answer: Long = resultArr[n]
        return answer
    }
  
}