[백준] (Swift) 11727번 - 2xn 타일링2 (스위프트, dp, 동적계획법 자세한 풀이)

문제 링크

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

11727번: 2×n 타일링 2

 

내가 푼 풀이

우선 이전 2xn타일링 문제에서는 규칙을 발견하고 그냥 피보나치 방식으로 풀었다. 이 문제는 그 문제의 연장선이기는 하지만, 피보나치 수열 규칙으로는 풀 수가 없었다. 정확하게 왜 그런 방식으로 문제를 풀었는지 이해하는 것이 중요했다..

우선 풀이에 앞서 경우의 수를 구하는 방식과 원리에 대해서 이해해보자.

[1, 2, 3, 4] 의 배열이 있을 때 , 이 숫자들로 만들 수 있는 순열을 작성해보면 다음과 같다.

• 1 2 3 4
• 1 2 4 3 
• 1 3 2 4
• 1 3 4 2
• 1 4 2 3
• 1 4 3 2
• 2....3. .... 4...  

이렇게 24가지가 나열될 것이다. 그럼 이때, 맨 앞이 1인 순열의 경우의 수를 구해보면, 1 빼고 나머지 2, 3, 4로 줄을 세우는 경우의수를 구하는 것이므로 3! , 즉 답 6을 구할 수 있다. 이처럼 '한가지를 고정하고' 경우의 수를 찾으면 (n-1)! 가 된다.

그렇다면, 2개의 수를 고정하고 경우의 수를 구하면 어떤가? 바로 (n-2)!가 될 것이다.

그럼, 위의 개념을 타일에다가 대입해보면, 맨 끝에 하나의 2x1 짜리 타일을 고정해둔 경우의수와, 2x2로 이루어진 타일을 고정해둔 경우의 수를 더하면 될 것이다. 이걸 도식화 하면, dp[i-1] 과 dp[i-2] 에 value로 넣을 펙토리얼 값을 구하면 된다는 것이다. 그림으로 살펴보자.

이렇게 된다. 맨 끝쪽을 고정해두고, 갯수를 구하면 각각 n-1 과 n-2를 기준으로 값을 구하게 된다. 두번째에 그려진 부분을 보면, n-1과 겹치기 때문에 경우의 수에서 빼준다고 하였는데, 생긴 모양이 맨위의 그림과 같기 때문에 결국 갯수를 동시에 센다면, 겹치게 될것이다. 따라서 위 그림 네 개중 세 가지만 더해주는 방식을 선택하여 문제를 풀 수 있다. 

소스코드는 다음과 같다.

let n = Int(readLine()!)!
var dp = [Int](repeating: 0, count: n+1)

if n == 1 {
    print(1)
} else if n == 2 {
    print(3)
} else {
    dp[1] = 1
    dp[2] = 3
    
    for i in 3..<n+1 {
        dp[i] = (dp[i-1] + 2*dp[i-2]) % 10007
    }
    print(dp[n])
}

 

생각보다 기초문젠데, 생각하기가 어려웠다. 지금까지 모두 인터넷을 참고하여 푼 풀이이기 때문에 복습을 몇 번 더 반복해야겠다.!! 꼮!!!