백준 11727: 2*n 타일링2

백준 2*n타일링 2

본문보기

https://www.acmicpc.net/problem/11727

dp문제. 경우의 수를 구하는 문제이다.

이 문제는 2*n 타일링 의 확장판 같은 문제이다. (브루드워?) 링크참조

이번엔 약간 다른것이 있는데 2*2 타일이 있기 때문에 a[n-2]의 경우의 수가 2개가 된다.

길이가 3일때를 생각해보자. 2까지 완성된 경우 세로로 길때 완성되는 경우와 1까지 완성된경우 가로로 긴 두개를 쌓아서 완성된경우, 2*2로 완성된경우 가 있다.

an 이 n 까지 완성된 블록의 경우의 수라고하자. a3 은 a2+ a1+ a1 으로 표현할 수 있다.

3부터 차근차근 경우의수를 기록해나가면서 다음 길이의 블록의 경우의 수를 구하려고하면 된다.

낮은 상태에서 부터 높은 상태로 까지의 값을 기로고해나가기 떄문에 bottom-up dp 문제라고 한다.

부가설명

bottom-up 의 반대 접근법으로는 up-bottom dp( 또는 memoization dp) 라고 한다. 이 두 접근방법은 결과적으로 또 수학적으로 동일하다(고 생각한다. 확실하진 않지만 ㅠ..ㅠ )

문제를 풀다가 느끼지만 memoization을 써야만 간단하게 풀 수있는 문제가 존재한다. 차차 알아 갈 것이다. 

2*n 타일링 문제와 더불어 간단한 점화식으로 문제를 해결할 수 있는 경우의 수(dp) 문제였다.

소스보기

https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/p11727.c