코후닝

알고리즘 분류: 다이나믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 【 풀이 】 역시 다른 DP문제와 마찬가지로, 경우의 수를 계산하면서 규칙을 찾는 것이 중요하다. 2*n 직사각형을 채우는 방법의 수를 저장한 배열을 N이라고 했을 때, N[4] 까지의 값들은 다음과 같다. 1 2 3 4 1 3 5 11 여기서, N[n] = N[n-2]*2 + N[n-1] 이라는 점화식을 도출할 수 있다. 즉 이에 따라 12까지의 값을 나열하면 다음과 같다. 3..