[Java / Kotlin] 99 클럽 코딩 테스트 스터디 미들러 22일차 - 멀리 뛰기

https://school.programmers.co.kr/learn/courses/30/lessons/12914?language=kotlin

프로그래머스

[문제]

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한 번에 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이 1이면 도달 가능한 방법은 1가지, 2이면 방법은 2가지, 3이면 3가지, 4이면 5가지....
효진이가 한 칸 또는 두 칸을 뛸 수 있기 때문에, n 칸에 도달하는 방법의 수는 n-1 칸에 도달하는 방법의 수와 n-2 칸에 도달하는 방법의 수의 합과 같습니다.

n이 3 이상일때 부터는 3부터 n까지 순회하면서 가지 수 % 1234567을 계산해 내어 최종 값을 반환하면 됩니다.

(f(n - 1) + f(n - 2)) % 1234567 

 

코틀린 코드입니다.

class Solution {
    fun solution(n: Int): Int {
        if (n == 1) return 1
        if (n == 2) return 2

        var a = 1
        var b = 2
        var temp = 0

        for (i in 3..n) {
            temp = (a + b) % 1234567
            a = b
            b = temp
        }

        return temp
    }
}

 

자바 코드입니다.

public class Solution {
    public int solution(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;

        int a = 1;
        int b = 2; 
        int temp = 0; 

        for (int i = 3; i <= n; i++) {
            temp = (a + b) % 1234567;
            a = b; 
            b = temp;
        }

        return temp;
    }
}

a와 b는 각각 n - 1, n - 2 방법의 도달 가능 수를 반영합니다.

그리고 두 가능 수를 더해서 문제에 제시한 대로 1234567로 나눈 나머지 값을 계산하고, 

이후 계산을 위해 b에 반영해줍니다.