[알고리즘][동적 계획법] 2xn 타일링 (백준)

다이나믹 프로그래밍(동적 계획법) 문제 - 2xn 타일링(백준)

동적 계획법의 가장 기본적인 문제가 아닌가 한다.

2xn 크기의 타일이 주어진다면 2x1, 1x2크기로 타일을 채울 수 있는 경우의 수를 모두 구하는 문제이다.

1. 2x1 크기 타일로 채우는 방법

2. 2x2(1x2 타일 두개)로 채우는 방법

위의 두가지 방법으로 분류하여 생각하면 쉽게 점화식을 찾을 수 있다.

동적 계획법의 기본 원리를 짚고 넘어가자면 차근차근 답을 찾아나가면서

그 답을 dp배열에 저장하고, 저장된 데이터를 통해 다음 답을 찾아나간다는 것이다.

n크기의 타일을 채울 수 있는 경우의 수는 

1. dp[n-1]의 경우의 수에 2x1 크기 타일을 하나씩 붙여주는 경우

2.  dp[n-2]의 경우의 수에 2x2 크기 타일을 하나씩 붙여주는 경우

dp[x]의 값에는 n이 x일 경우의 모든 경우의 수가 들어가 있다. 

따라서 dp[10]의 값을 찾는다 하면 

dp[9]에 2x1타일을 하나 붙여주는 경우 + dp[8]에 2x2타일을 하나 붙여주는 경우이다.

해당 인덱스의 dp에는 모든 경우의 수가 들어있다는 보장이 있기 떄문에

dp[n] = dp[n-1] + dp[n-2] 라는 점화식이 성립하게 된다.

다이나믹 프로그래밍 - 2xn 타일링(백준)

소스 코드

코드는 굉장히 짧지만 점화식을 생각해내는 시간이 꽤 오래 걸렸다.