백준 11726번 2×n 타일링

문제

문제 출처 : https://www.acmicpc.net/problem/11726

풀이 과정

동적 계획법을 이용해서 2×N 크기의 타일을

dp[N-1] + dp[N-2]의 두가지 하위 문제로 만들어서 푼다

예시

dp[0] , dp[1]은 1로 설정하면

N이 2일때 dp[2] = dp[1] + dp[0] = 2

N이 3일때 dp[3] = dp[2] + dp[1] = 3

가 된다.

그러므로

dp[N-1] + dp[N-2] 는 2×N 크기의 타일을 채우는 경우의 수가 된다.

C++ 소스코드