간만의 알고리즘 공부 - 9 (멀리 뛰기 | 피보나치 수열)

문제 설명
효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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칸 or 2칸을 갈 수 있다고 해서 수식으로는 다음과 같이 도출했다

n = 1X * 2Y

 

그래서 n 에 따라서 X, Y 의 숫자가 나오게 되고 그걸로 일일히 표시해서 푸는 형태로 가능하다는것만 인지하고 더이상의 진척이 없었다.

 

코드 첨삭

fun solution(n: Int): Int {
    // 배열을 생성하고 초기값 설정
    val dp = IntArray(n + 1)
    dp[1] = 1
    if (n > 1) {
        dp[2] = 2
    }

	if (n > 2) {
        // 피보나치 수열을 기반으로 방법의 수를 계산
        for (i in 3..n) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567
        }
    }
    
    // 결과 반환
    return dp[n]
}

 

 

피보나치 수열로 접근해야한다는것 조차 몰랐다. 수학적 지식이 완전 0에 수렴한지 오렌지이기 때문에...

https://ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98

피보나치 수 - 위키백과, 우리 모두의 백과사전

 

피보나치수열을 적용과 별개로 1234567을 왜 끝에만 나누지 않고 매번 나누는것에 대해서 이해가 가지 않아서 여러번 질문을 통해서 알게된 점은 아래와 같다.

- '정수 범위 초과 방지', n이 커지면 계산 중간에 숫자가 매우 커질 우려가 있다

- '성능 최적화', 매번 큰 숫자를 나누는 것보다 작은 숫자를 나누는 것이 더 빠르기 때문

 

추가적으로 여기서 내가 추가한 코드는 분기문 if(n>2) 이다. 일단 제한 사항으로 n은 1 이상의 정수라고 했기 때문이다.