백준 문제풀이/SILVER
[백준 / BOJ / SILVER 3] 11727 번 : 2xn 타일링 2
https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 문제 접근법 점화식을 세워 접근 하면 된다. 2xn의 직사각형이 있을 때 마지막에 1x2 타일이 없다고 가정하면 그 직사각형은 가로길이 n-1까지의 경우의 수 라고 볼 수 있다. 같은 경우로 2x1 짜리 타일이 없으면 가로길이 n-2까지의 경우의 수 라고 볼 수 있다. 단, 2x1 타일 대신 2x2 타일을 사용할 수도 있으므로 DP[N](2xn 까지의 경우의 수) = DP[N-1] + DP[N-2] * 2가 성립한다. 아래는 ..
