[백준] 11726번 : 2xN타일링

11726번: 2×n 타일링

11726번: 2×n 타일링

🤔 문제분석

이번 문제는 문제의 아이디어가 떠올리지 않아서 인터넷검색을 통해 흰트를 찾았습니다. 제가 찾아본 흰트중 가장 이해가 잘 되었던 내용을 이야기하고자 합니다.

어떠한 수열이 있다고 가정해봅니다. [1, 2, 3, 4, 5] 수열이 주어졌을때 여기서 순열의 가지수는 5! 입니다. 하지만 [1, 2]는 고정되어있다고 가정하고 나머지의 수열을 구한다면 3!이 되겠습니다. 이렇게 숫자가 이미 고정되어있는 사고 방식을 해당 문제에 적용해봅니다.

n이 3일때를 주목해보자, n이 1일때에 2*1 타일을 붙히고, n이 2일때의 1*2 타일을 붙혀서 만들 수 있습니다. n이 4일때도 마찬가지로 n이 2일때에 2*1타일을 붙히고, n이 3일대의 1*2 타일을 붙혀서 만들 수 있습니다. 위의 내용에서 제가 예를들었던 순열의 문제를 적용하여 생각해보면, n이 3일때 구하는방법은 이미 고정되어있는 n이 1상태에서 21 타일을 붙히고, 이미 고정되어있는 n이 2인 상태에서 12 상태를 붙혀서 만들었기때문에 우리는 다음과 같은 점화식을 도출 할 수 있습니다.

dp[n] = dp[n-1] + dp[n-2]

 

📝 의사코드

1. 다이나믹 테이블을 생성한다. ( 인덱스를 하나를 늘렸다 )
2. dp[1] = 1, dp[2] = 2 값으로 초기화 한다. ( 타일의 개수 초기화 )
3. 이제 3 부터 n까지 순회하면서 위의 도출한 점화식을 적용한다.
4. dp[n] 값을 출력한다.

💻 코드

import sys
input = sys.stdin.readline
n = int(input())
dp = [0 for _ in range(n+1)]

if n >= 3:
    dp[1] = 1
    dp[2] = 2
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2]

    print(dp[n] % 10007)
else:
    if n == 1:
        print(1)
    else:
        print(2)

🎯 피드백 및 개선사항

다이나믹 프로그래밍 문제를 쉽고 빠르게 문제를 풀기 위해서는 위의 설명한바와 같이 어떠한 규칙을 찾아야한다. 그 규칙을 도출하는 과정이 문제 해결의 전부이고, 도출하는 과정과 방식을 이해해야, 다른 문제의 유형을 접근할때 풀 수 있다.