문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 다이나믹 프로그래밍 방법 기본적인 다이나믹 프로그래밍 방법은 계산을 용이하게 하는데에 있다. 즉, 일반적인 완전탐색처럼 모든 계산을 다 하되, 다이나믹 프로그래밍의 간단한 개념은 주어지는 모든 계산을 하지 않고, 필요한 계산이 있으면 재사용하는 것이다. 간단히 예를들어, 피보나치수열처럼 같은 계산 구조가 반복될 경우, 새로운 해를 구할 때마다 모든 계산을 반복하지 않고 1번 계산했던것을 재사용한다면 계산량을 엄청나게 줄일 수 가 있다. 풀이 (1) 직사각형을 채우는방법은 2가지 밖에 없다. 1x2 타일을 1개 두거나 2x1 타일을 위아..