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

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

 

비고:

-Dynamic programming 활용

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

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

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

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

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

 

내소스코드:

boj.kr/a173cca197ca42eb88e87bd88c47a6ba

공유 소스 보기