11726번 Python

이 문제는 어렴풋이 기억나긴 했지만 다시 정리하겠다. 아마 실제로 그려보면 조금 더 빨리 풀 수 있는 것으로 알고 있다.

 

문제의 의도는 1x2, 2x1 블록으로 2xn의 직사각형을 채울 수 있는 최적의 해를 구하는 문제이다. 실제로 그려보면서 유추되는 식을 찾아보는 것이 메인 포인트이다.

 

2x1 직사각형의 경우에는 1가지, 2x2의 경우에는 2가지의 형태를 알 수 있다. 2x3의 형태까지만 그려보자.

 

이렇게 그렸을 경우에도 고려해보자. 무언가 특징이 하나 존재하는데 여기서도 보이지 않는다면 정말 마지막으로 2x4 직사각형까지 그려보자.

 

개수를 잘 세어보면 피보나치 수열의 형태와 유사한 것을 알 수 있다. 하지만 단순히 시각적으로 보이는 걸 토대로 개수를 세어가는 것보다는 뭔가 더 정확하게 그려지는 형태를 찾아보는 것이 더 나을 수도 있는 방향이다.

 

이렇게 놓고 본다면 조금 더 피보나치 수열의 형태를 띄는 이유를 잘 알 수 있을 것이다. n에 해당하는 부분은 n-1에 해당하는 타일을 모두 사용했고 n-2에 해당하는 타일을 모두 사용했다.

 

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

그렇기에 이런 점화식을 구할 수 있는 것이다.

 

import sys

n = int(sys.stdin.readline())
dp = [0] * 1001
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)

그렇기에 코드로 이를 구현한다면 다음과 같이 구할 수 있게 되는 것이다.