[DP-예제 1] 블럭채우기

동적 계획법의 예제인 블록채우기에 대해서 공부하면서 DP를 공부해 보자.

세로 길이가 2 이고, 가로 길이가 N 인 블럭에 세로 2, 가로 1의 블럭을 채우는 경우의 수를 구하는 예제이다.

쉬운 이해를 위해서 입력 N 이 4일 때(가로 길이가 4) 블럭을 채우는 경우의 수는 5이다.

 

블럭을 채우는 방법을 보면 이러한 식으로 채울 수 있는 방법이 생각해 보면 5가지가 있다.

그런데 이 문제를 코딩으로 어떻게 해결 할 수 있을까?

블럭 채우기 알고리즘을 세울려면 먼저 전체 경우를 어떻게 나눌 것인지 생각해야 한다.

이 부분이 동적 계획법에서 가장 생각 해 내기 어려운 부분 문제를 정의하는 과정이다.

모든 경우의 수를 보면 위와 같은데, 어떻게 기준을 세우냐면 가장 마지막에 들어가는 블럭을 본다.

그러면 1개가 세로로 세워진 블럭과, 가로로 눕혀진 블럭 2개가 마지막에 채워진 두가지 경우를 볼 수 있다.

이렇게 두 가지 기준을 세워서 동적 계획법으로 문제를 해결해 보자.

위와 같이 두가지로 나눠서 경우의 수를 구해보면,

① 마지막 블럭을 빼고 나머지 가로2 세로3 인 블럭을 채우는 경우의 수

+

② 마지막에 가로로 눕혀진 2개의 블럭을 제외한 나머지 가로2 세로2인 블럭을 채우는 경우의 수

이 두가지 경우를 합치면 모든 경우의 수가 나오게 된다.

이제 문제를 이해 했으므로, 블럭 채우기 문제를 동적계획법 절차를 통해 해결해 보자.

T(i) 를 2 × i 블럭을 채우는 경우에 수라고 정의하자.

이해를 돕기 위해 T(2) 는 2 × 2 블럭을 채우는 경우의 수 이므로 세로로 세운 블럭2개, 가로로 누운 블럭 2개를 넣으면

채워지므로 경우의수가 2가지이고,

T(3) 은 3 × 3 블럭을 채우는 경우의 수 이므로 위의 그림을 보면 3가지가 나오는 것을 알 수 있다.

부분 문제를 정의 했으므로 이제 점화식을 구할 차례인데, 2 × 4 블럭을 채우는 것을 예제로 들면

마지막에 세운 1개의 블럭의 나머지 공간은 2 × (i-1) 의 공간을 채우는 경우의 수를 구하면 된다.

이는 우리가 부분 문제를 정의한 식에 따라 T(i-1) 로 표현할 수 있다.

다음으로 눕힌 블럭2개로 채우는 경우의 수는 2 × (i-2) 블럭을 채우는 경우의 수를 구하면 되므로

T(i-2) 라고 표현 할 수 있다.

두 가지 경우를 더하면 2 × 4 의 블럭을 채우는 모든 경우의 수를 구한다고 할 수 있다.

결론적으로 이를 통해 점화식을 세우면 2 × i 의 상자를 채우는 경우의 수는

T(i) = T(i-1) + T(i-2) 라고 세울 수 있다.

어디서 많이 본 식이 보이는데, 블럭채우기 문제가 피보나치 수열 문제와 같다는 것을 볼 수 있다.

이제 마지막 단계로 문제를 해결 해 보면 피보나치 수열과 마찬가지로 가로의 길이가 1일 때, 2일 때는 초기값이 필요하므로

초기값으로 각각 1과 2를 넣어주고, 2 × 3 부터는 쉽게 첫번 째 항과 두번 째 항을 더하여 쉽게 구할 수 있다.

출처 : Algorithm LABS