[백준 11726] 2xn 타일링 (Kotlin 풀이)

1.문제 

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

2. 입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

3. 출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

---

4. 포인트

1. 1. 점화식을 세울 수 있어야한다 
      1. dp[ n+2 ] = (dp[ n+1 ] + dp[ n ]) / 10007
   2. 10007 로 나눔 다는 의미를 파악한다.

4. 문제 풀이

그림을 그려가며 규칙 찾아 점화식을 세울 수 있엇다. 어떤 원리인지는 파악하지 못했지만 규칙을 찾아 낼 수 있었다. 

문제는 10007 로 나눈다는 의미를 파악하지 못해 조금 헤매었다.

 

문제에서 10007 로 나눈 값을 요했다는 것은 너무 큰 값으로 인해 오류가 날 수 있는 가능성이 있는 것을 의미한다,

처음에는 마지막 값만 나누어 주었지만 중간 값이 int 범위를 벗어나 오류가 난 것 같다.

점화식을 보면 dp 에 값을 저장 할때에도 나눗셈을 적용해주어도 결과에 영향을 주지 않는 다는 것을 알 수 있다.

 

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {

    val n = readLine().toInt()

    if (n <= 3) {
        println(n)
    } else {
        val dp = IntArray(n + 1)
        for (i in 0..2) {
            dp[i] = i
        }
        if (n >= 3) {
            for (i in 3..n) {
                dp[i] = (dp[i - 1] + dp[i - 2])%10007
            }
        }
        println(dp[n] )
    }
}