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

thumbnail

안녕하세요. 이번에는 프로그래머스 멀리 뛰기 문제를 풀어보려고 합니다.

 

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

프로그래머스

---

Problem

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한 번에 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 이하인 정수입니다.

사진 1. 입출력 예

---

Solution

class Solution {
    fun solution(n: Int): Long {
        var arr = LongArray(2001)
        
        arr[0] = 0
        arr[1] = 1
        arr[2] = 2
        
        for(i in 3..n) {
            arr[i] = (arr[i - 1] + arr[i - 2]) % 1234567
        }
        
        return arr[n]
    }
}

 이번 문제는 DP로 문제를 풀면 쉽게 풀 수 있습니다. 

1칸	2칸	3칸	4칸	5칸
1	1 + 1	1 + 1 + 1	1 + 1 + 1 + 1	1 + 1 + 1 + 1 + 1
	2	1 + 2	1 + 1 + 2	1 + 1 + 1 + 2
		2 + 1	1 + 2 + 1	1 + 1 + 2 + 1
			2 + 1 + 1	1 + 2 + 1 + 1
			2 + 2	2 + 1 + 1 + 1
				1 + 2 + 2
				2 + 2 + 1
				2 + 1 + 2
1	2	3	5	8

이렇게 보면 우리는 dp식을 구할 수 있습니다. dp [n] = dp [n - 1] + dp [n - 2]를 알 수 있습니다. 그래서 우리는 이 공식을 사용해서 코드를 작성하면 됩니다. 이 문제를 보니까 예전에 풀었더 피보나치 수의 문제가 생각나네요. 피보나치가 궁금하신 분은 한번 아래의 링크를 들어가 보면 도움이 될 것 같습니다. 

[프로그래머스] 피보나치 수 Kotlin

 

1. 다른 사람 코드

class Solution {
    fun solution(n: Int): Long = getFibonacci(n + 1)
    private tailrec fun getFibonacci(currentNumber : Int, acc : Long = 0, prevSum : Long = 1) : Long =
        if(currentNumber == 0) acc
        else getFibonacci(currentNumber - 1, prevSum, (prevSum + acc) % 1234567)
}

  오늘도 다른 사람의 풀이가 궁금해서 공부해보려고 합니다. 위에 말한 것 처럼 이분은 피보나치 수와 비슷하게 문제를 푼 것을 알 수 있습니다. 여기서 tailrec 꼬리 재귀의 모습도 확인할 수 있었습니다. 꼬리 재귀가 궁금하신 분은 아래의 링크를 보고 오시면 좋을 것 같습니다.

[Kotlin] tailrec 꼬리 재귀 함수에 대하여 알아보기

---

Performance

1. 내가 작성한 코드	2. 다른 사람 코드