목록dp (1)

DonHurry

[Python] 백준 2133번 - 타일 채우기

📖 문제 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 🔎 풀이 DP 문제로, 점화식을 찾아야 합니다. 우선 홀수인 경우 타일을 채우기가 불가능하므로 경우의 수를 0으로 두고, N이 2의 배수일 때만 생각하면 됩니다. N = 2 일 때는 아래와 같이 3가지 경우로 나눌 수 있습니다. 따라서 dp[2] = 3 이 됩니다. 다음으로 N = 4 일 때에는 아래와 같이 3가지 경우로 생각해볼 수 있습니다. 앞서 dp[2]가 3이었으므로, 경우의 수는 3 * 3 + 2 = 11 가지가 됩니다. N = 6 일 때에는 먼저 dp[N-2] * dp[2] 를 생각할 수 있습니다. 여기에 위에서 보았던 특수한 경우 2가지를 더 생각해야..
Problem Solving 2024. 1. 22. 13:41
이전 Prev 1 Next 다음