[알고리즘풀이 with Python] 백준 11727번

설명 2×n 직사각형을 1×2, 2×1, 2×2 타일로 채우는 방법의 수를 구하는 문제다. 이를 다이나믹 프로그래밍(DP)을 활용하여 풀었다.

초기값으로 dp[0]은 0, dp[1]은 1, dp[2]는 3으로 설정한다. 그리고 점화식을 적용한다. 2×n 크기의 직사각형을 채우는 방법의 수는 3가지다. 1. n-1까지 채운 후, 2×1 타일 하나를 추가하는 경우 2. n-2까지 채운 후, 2×2 타일 하나를 추가하는 경우 3. n-2까지 채운 후, 1×2 타일 둘을 추가하는 경우 따라서, n-1까지 채운 후의 경우의 수는 dp[i-1] 개, n-2까지 채운 후의 경우의 수는 dp[i-2] * 2이다.

이 두 값을 더해서 dp[i]에 저장한다. ※ 문제에서 출력 조건을 보면 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지 값을 출력하라고 되어있다. 그 이유는 수가 매우 커질 경우에는 정확한 값이 나오지 않을 수 있기 때문이다.

풀이 import sys input ...

요청 처리 중입니다...

[알고리즘풀이 with Python] 백준 11727번 - 2×n 타일링 2

등록된 다른 글