[Algorithm]백준, 11727, 2×n 타일링 2

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

 

비고:

-Dynamic programming 활용

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

점화식을 D[n] = D[n-1] + (D[n-2] * 3) 에서  *3로 생각하면 안됨

(D[n-2]에서 2x1을 2개, 1x2을 2개, 2x2을 1개 사용하는 방식 총 3가지니까 *3하려고한다면, 3개 중 첫번째는 D[n-1]에서 count해서 중복발생)

따라서 D[n] = D[n-1] + D[n-2]*2

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

 

내소스코드:

boj.kr/d99f1a90f14341a090c4ba58bd460c33

공유 소스 보기