2024.06.14 TIL 코트카타 82번(멀리뛰기)

    fun solution(n: Int): Long {
        if(n == 1)
            return 1

        val numJumpWay = LongArray(n+1)
        numJumpWay[1] = 1
        numJumpWay[2] = 2

        for(numJumpWayIndex in 3..numJumpWay.size-1) {
            numJumpWay[numJumpWayIndex] = (numJumpWay[numJumpWayIndex-1] + numJumpWay[numJumpWayIndex-2]) % 1234567
        }

        return numJumpWay[n]
    }

 

풀이 과정

- 문제에서의 경우의 수를 n이 8일 때까지 손으로 직접 해본다.

- n이 증가할 때마다 규칙성이 있는지 확인한다.

- [n] = [n-1] + [n-2] 임이 확인되어 배열을 만들어 반복문을 돌린다.

 

포인트

- 완전 탐색 문제가 아닐까 생각했지만 n의 최댓값(2000)일 때 완전 탐색은 시간 초과가 될 가능성이 높았기 때문에 다른 방법을 생각했고 그 것이 규칙성을 찾는 DP가 정답이었다.

- 다른 방식으로 직접 계산 식을 만들어 풀 수도 있다.