[백준] 11727번: 2×n 타일링 2

💻 문제 - S3

3가지 종류의 타일로 채우는 방법의 수를 구하는 프로그램이다. n을 1부터 증가시키면서 규칙을 찾아보려했으나 쉽지 않았다. 그래서 n이 k일 때 어떻게 되는지 3가지로 나누어서 비교했다.

• k-1일 때 + 1x2 타일
• k-2일 때 + 2x1 타일 * 2
• k-2일 때 + 2x2 타일

이를 통해, dp[k] = dp[k-1] + 2 * dp[k-2]라는 점화식을 얻었다(이것도 bottom-up).

n이 1일 때 1, n이 2일 때 3, n이 3일 때 5이므로 점화식을 검산할 수 있고 dp를 [0, 1, 3]로 초기화할 수 있다.

👉 제출 코드

n = int(input())
dp = [0, 1, 3]
for i in range(3, n+1):
    dp.append(dp[i-1] + 2 * dp[i-2])
print(dp[n]%10007)

🙏 다른 사람의 풀이 보기

n = int(input())
dp = [0,1,3,5] + [0] * (n+1)
for i in range(3, n+1):
    dp[i] = dp[i-1] + dp[i-2]*2
print(dp[n] % 10007)

• 미리 배열을 할당해주고 값을 대입하는 경우가 시간이 더 효율적이다.

👀 참고 자료

• [백준 11727 : PYTHON] 2xn 타일링 2