백준 11727 2n 타일링 파이썬

백준 11727번 2n타일링 풀이

접근방식

1. 1<= n <= 4 의 경우의 수를 직접 그려본다.
2. 안에서 규칙성을 찾는다.

n이 1씩 증가할 때마다 이전에 사용된 타일의 경우의 수가 유지된다는 규칙을 발견할 수 있습니다.
하지만, 2x1처럼 세로로 긴 타일은 바로 이전 (n-1)의 경우의 수와 동일하게 유지되지만,
두칸의 여유(n-2)가 생기면 2x2 타일과 1x2 타일로 구성할 수 있기 때문에 n-2의 두배의 경우의 수가 나옵니다. 즉, dp[n] = dp[n-1] + (dp[n-2]2)** 라는 점화식을 도출할 수 있습니다.
dp[n-1] : 바로 이전의 경우의 수에 2x1의 타일을 붙이는 경우
dp[n-2] : n-2라는 것은 결국 2칸의 여유를 고려했을 때 2x2 타일과 1x2 타일을 사용할 수 있는 경우

# 입력받기
import sys

input = lambda: sys.stdin.readline().rstrip()

n = int(input())

MOD = 10007

# dp 리스트 선언
dp = [0 for _ in range(1001)]

dp[1] = 1

dp[2] = 3

for i in range(3, n+1):
    dp[i] = (dp[i-1] + dp[i-2] * 2) % MOD

print(dp[n])

해당 문제는 실버3레벨에 해당하므로 어렵지 않게 풀 수 있는 문제였습니다.

다이나믹 프로그래밍의 개념을 잘 적용할 수 있는 문제라고 생각합니다.

이 문제도 4번 정도 풀었는데 풀 때마다 헷갈리는 부분이 생겼었지만,

이제는 완전히 이해하고 넘어갈 수 있었습니다.

알고리즘도 모든 것과 마찬가지로 꾸준한 연습과 이해를 바탕으로 실력이 향상합니다. Just do it & Keep steady