[Swift] BOJ 11726 2 x n 타일링

BOJ 11726 2 x n 타일링

 

✅ BOJ 11726 2 x n 타일링

이 문제는 생각보다 어려웠다. 사실 나동빈 알고리즘 dp편에서 본 기억이 있는데, 이를 직접 풀어보려니까 도저히 생각이 나지 않았다.

사실 책의 해설도 잘 이해가 가지 않았는데, dp를 보면 볼수록 수학적인 사고가 강력하게 필요한 것 같다.

 

풀이와 해설이 이해가 가지 않아서 다른 분의 블로그를 참고하였다.

 

1x2, 2x1 두개의 타일이 있다.

n = 1 : | 1개

n = 2 : ||, = 2개

n = 3 : |||, =l, l= 3개

n = 4 : llll, ll=, l=l, =ll, == 5개

n = 5 : lllll, lll=, ll=l, l=ll, =lll, l==, =l=, ==l 8개

 

이런 패턴을 찾을 수 있다.

참고한 블로그에서는 순열의 원리, 나동빈 책(약간은 문제가 다르다!)에서는 점화식을 만드는 사고를 제시해 주었다.

하지만 난 dp를 풀때는 저렇게 하나하나 몇몇 케이스를 만들어서 규칙성을 찾는게 제일 빠른거 같다

 

   let input: Int! = Int(readLine()!)
        
        var dp: [Int] = [Int](repeating: 0, count: 1001)
        dp[1] = 1
        dp[2] = 2
        
        if input >= 3 {
            for i in 3...input {
                dp[i] = (dp[i-1] % 10007) + (dp[i-2] % 10007)
            }
        }
        
        print(dp[input] % 10007)
    }

 

 

(참고) https://kosaf04pyh.tistory.com/222

[알고리즘 문제] 백준11726 - 2xn 타일링