코후닝

알고리즘 분류: 다이나믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 【 풀이 】 DP 문제이다. 다른 문제들과 마찬가지로 처음부터 경우의 수를 따져가며 규칙성을 찾는 것이 중요하다. 결론적으로는 이 문제는 피보나치수열의 형태를 보인다. N[1] = 1 N[2] = 2 N[3] = 3 N[4] = 5 N[5] = 8, N[6] = 13, N[7] = 21, N[8] = 34, N[9] = 55 즉 N[n] = N[n-2] + N[n-1]...