문제 https://www.acmicpc.net/problem/11727 풀이 n = int(input()) dp = [-1]*(n+1) dp[0] = 1 dp[1] = 1 for i in range(2,n+1): dp[i] = 2 * dp[i-2] + dp[i-1] print(dp[n]%10007) 이 문제에서 2×N을 채우는 경우의 수는 세가지로 나뉜다. 1) 2×(N-2)를 채우고 = 모양을 더하는 경우 2) 2×(N-2)를 채우고 ㅁ 모양을 더하는 경우 3) 2×(N-1)을 채운 뒤 l 모양을 더하는 경우 즉, 2×N을 채우는 경우의 수는 2×(N-2)를 채우는 경우의 2배에 2×(N-1)을 더한 값이다. N=1일때 경우의 수는 1, N=2일때 경우의 수는 3이라는 것을 기본값으로 해서 동적계획법..

문제 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 풀이 n = int(input()) dp = [-1]*(n+1) dp[0] = 1 dp[1] = 1 for i in range(2,n+1): dp[i] = dp[i-2] + dp[i-1] print(dp[n]%10007) 이 문제의 정답 코드는 피보나치 수열을 구하는 방식과 동일하다. 그 이유를 살펴보자면 2×N을 채우는 경우의 수는 아래 두가지로 나뉜다. 1) 2×(N-2)를 채우고 = 모양을 더하는 경우 2)..