백준 11726 : 2*n 타일링

백준 2*n 타일링

본문보기

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

dp문제. 경우의 수 문제이며, 점화식을 구하는 문제이다. 이 문제의 형식은 다음 문제와 유사하다.

n 길이의 비트스트링 문자열의 경우의 수를 구하여라. 단 0이 두개 이상 연속하면 안된다.

우선 n길이의 비트스트링 문자열 경우의 수는 2^n 이다. 그런데 0이 연속되면안된단다. 확실히 2^n보다 작을것 같지만 경우의 수가 몇개인지 모른다.

여기서 접근법은 이전 문제(1로만들기)처럼 차근차근 접근하는 것이다. 문자열 3일 때의 경우의 수를 생각해보자.

문자열 3일때의 경우의수는 3번째 수가 1인경우와 3번째 수가 0인경우로 표현할 수 있다. 3번째 수가 0일때에는 반드시 2번째 수는 1이 되어야한다. 

그리고 물음표인 곳은 반드시 건전한 비트스트링(연속해서 0이 나오지 않는 비트스트링)이 들어와야한다. 

an 이 n 길이의 건전한 비트스트링의 경우의 수 라고 하자. 이 때 우리는 3번째 길이는 a(2) + a(1) 임 을 알 수 있다.

사담이 본문보다 길었지만, 같은 맥락이였다.

n 길이의 블록을 만들기 위해선 다음과 같은 경우로 나뉜다. n 길이의 나무 블록을 만들기 위해서는 n 번째 나무 블록이 n-1길이에서 세로로 긴것으로 완성되거나 n-2 길이에서 가로로 긴것 두개를 쌓음으로 완성됨을 알 수 있다.

따라서 점화식은 다음과 같다. a[n] = a[n-1] + a[n-2]

물론 이 점화식은 3부터 차근차근 쌓아 올라가야 건전한 점화식이라 할 수 있다.

* 경우의 수(dp) 문제는 항상 굉장히 큰수가 따라오며, mod 연산이 나오기 때문에 주의하는 것이 좋다.

소스보기

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