백준 1309 동물원 Kotlin

문제

https://www.acmicpc.net/problem/1309

1309번: 동물원

어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.

이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.

동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.

 

 

문제 풀이

 

 

a를 사자를 배치하는 경우의 수라고 했을 때, a1은 위에서 보는 거와 같이 3개이고, 

a1 ~ a4 은 아래와 같다.

a1 ~ a4

그림를 통해 규칙을 찾아 보면

a1 = 3 = 3

a2 = 3 + 2 * 2 = 7

a3 = 3 * 3 + 2 * 4 = 17

a4 = 3 * 7 + 2 * 10 = 41

 

점화식

위의 식을 얻을 수 있다.

 

정답 코드

 

class Zoo{
    fun solution(){
        var N = readln().toInt()
        var dp = MutableList(N+1){0L} 
        dp[0] = 3L
        dp[1] = 7L
        if(N <= 2){
            println(dp[N-1])
            return
        }
        for(i in 2 until N) {
            dp[i] = (dp[i-2] + 2 * dp[i-1]) % 9901L
        }

        var answer = dp[N-1]
        println(answer)
    }
}

fun main() {
    var zoo = Zoo()
    zoo.solution()
}

 

시행착오 

dp에 9901의 나머지를 저장하는 게 아니라 출력할 때만 9901의 나머지를 구했었다. 이렇게 하면 계속 오류가 났었다.

https://www.acmicpc.net/board/view/70595

글 읽기 - 계속 런타임에러랑 메모리초과가 뜨는데... 잘못된 부분좀 알려주세요 ㅠㅠ

위의 글에서  "숫자를 저장할때 그대로 저장하시면 후반으로 갈수록 숫자가 너무 커져서 메모리를 과다하게 사용하게 됩니다. 이를 방지하기 위해서 중간중간 나머지 연산을 통하여 숫자의 용량을 줄여주셔야 합니다" 라는 글을 통해 왜 오류가 나는지 알 수 있었다.

 

https://www.acmicpc.net/board/view/119944

글 읽기 - DP 매우 큰 수, 나머지만 사용시 동일 결과 보장 이유

두번째로 위의 질문글과 같은 궁금증을 가지고 있었다. 결과값의 나머지를 구한 것과 나머지의 나머지랑 왜 같은지 이해가 가지 않았다.

즉, 아래 두 코드가 같은 결과를 가진다는 것이다. 

for(i in 2 until N) {
            dp[i] = (dp[i-2] + 2 * dp[i-1]) % 9901L
        }

var answer = dp[N-1]

for(i in 2 until N) {
            dp[i] = (dp[i-2] + 2 * dp[i-1]) 
        }

var answer = dp[N-1] % 9901L

찾아보니 모듈러 산술이라는 개념을 알면 저절로 이해가 되는 것이었다!

https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-addition-and-subtraction