[BOJ/백준][Silver3] 11726: 2xn 타일링(Kotlin)

백준 11726번 2xn 타일링

 

문제

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

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

 

---

입출력

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

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

 

입력	출력
2	2
9	55

---

접근방법

우리가 구해야하는 것은 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수이다.

일단 그림을 그려보았다. 그림을 그리다보니 규칙이 조금 보였다

2xn은 N - 1번째보다 한칸 늘어난 것이기 때문에

N - 1번째 경우의 수에 2x1 타일을 붙이는 방법(세로 타일 | 붙이기)과

N - 2번째 경우의 수에 1x2 타일을 붙이는 방법(가로 타일 = 붙이기)을 통해 만들 수 있다

따라서 DP식은 dp[n] = dp[n - 1] + dp[n - 2]

---

코드

import java.util.*

fun main(){
    val sc: Scanner = Scanner(System.`in`)
    var n = sc.nextInt()
    
    var dp = IntArray(n + 1){
        if(it == 1) 1
        else if(it == 2) 2
        else -1
    }
    
    for(i in 3..n){
        dp[i] = (dp[i - 1] + dp[i - 2]) % 10007
    }
    println(dp[n])
}

---

틀린 부분과 느낀 점

• 문제 출력 조건이 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지이기 때문에 dp값을 구할 때        n번째 값 % 10007연산을 해줘야 한다. 이걸 안하고 그냥 출력할 때 %연산했더니 틀렸다ㅜ
• 배열을 선언만하고 dp[1]과 dp[2]를 나중에 초기화했는데 계속 런타임 에러가 떴다. 이유는 입력값 n이 1일 때 dp는 크기가 2인 배열이 된다. 그런데 그 상태로 dp[2] 에서 index가 넘어가서 예외가 발생하는 것이다. 지금까지는 iterator로 초기화해서 에러가 안났었다.... 항상 배열을 사용할 때는 index와 bound를 잘 고려해야겠다고 다시한번 느꼈다..!!