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

백준 11727번 2xn 타일링2

 

문제

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

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

---

입출력

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

출력 : 첫째 줄에 2xn 크기의 직사각형을 채우는 방법의 수를 10007로 나눈 나머지를 출력한다

입력	출력
2	3
8	171
12	2731

---

접근방법

이 문제도 2xn타일링 문제와 비슷하다

문제를 살짝 변형한 느낌,,

어제 풀었던 2xn타일링 문제는 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하는 문제였고

이 문제는 1x2, 2x1, 2x2 타일로 직사각형을 채우는 방법의 수를 구하는 문제이다

다른점이라면 2x2타일이 추가되었다는 것이다

 

이 문제를 풀 때 2xn 타일링과 같은 방법으로 접근했다

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

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

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

여기까지는 2xn타일링과 똑같고 이 문제는

N - 2번째 경우의 수에 2x2 타일을 붙이는 방법(네모 타일 ㅁ붙이기)

 

따라서 dp식은 dp[n] = dp[n - 1] + dp[n - 2] x 2가 되는 것이다

---

코드

import java.util.*

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

 

---

한 번 풀어봤던 문제유형이라서 그런지 푸는데는 그리 오래 걸리지 않았다

dp문제를 풀면서 든 생각인데 dp는 아이디어가 중요한 것 같다.

그래서 풀면서 답답하더라도 끝까지 생각해보려고 노력했다

답을 보면 그 문제를 푸는 아이디어를 스포당하는거니까,,

문제를 많이 풀어서 마스터하고싶다,,,,,ㅜ