[Algorithm]백준, 2133, 타일 채우기

문제:https://www.acmicpc.net/problem/2133

 

비고:

-Dynamic programming 활용

-bottom-up이어서 왼쪽에서부터 오른쪽으로 타일이 하나씩 늘어나는 상황 생각해서

점화식을 D[n] = 3*D[n-2] + 2*D[n-4]로 생각했다가 고생했다.

여기서 3은

--

||

||케이스와

 

--

--

--케이스

 

||

||

--케이스 해서 총 3가지

 

2는

----

|--|

|--|와

 

|--|

|--|

----

 

이 때 n=6일 때 고려하지 못한 케이스가

------

|----|

|----|와

 

|----|

|----|

------이다.

 

따라서, 경우를 나눌 때, 우측 상단에 --로 시작해서

--

--

--로 끝나는 경우와

 

--

 |

 |

그리고

 |

--

--인 경우, 근데 마지막 2가지는 상하대칭성을 띄니까 1개의 함수로 세자

따라서, 구하고자하는 ans(n)과 보조함수 aux(n)을 정의

ans(n) = ans(n-2) + aux(n-1)

aux(n) = ans(n-1) + aux(n-1)

ans(0) = 1, ans(1) = 0

aux(0) = 0, aux(1) = 1로 두고 풀면 된다.

 

-매 결과를 저장할 배열같은게 필요하지 않음, 마지막 가짓수만 새면 됨

 

내소스코드:

boj.kr/7be8dbc0db4445888d24df8c7db663e8

공유 소스 보기