728x90
문제: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
공유 소스 보기
www.acmicpc.net
728x90
'CS' 카테고리의 다른 글
| [Algorithm]백준, 14852, 타일 채우기 3 (0) | 2020.10.10 |
|---|---|
| [Algorithm]백준, 2133, 타일 채우기 (0) | 2020.10.10 |
| [Algorithm]백준, 11726, 2×n 타일링 (0) | 2020.10.10 |
| (미완)[Algorithm]알고리즘의 유형, 알고리즘 문제의 유형 (0) | 2020.10.10 |
| [Python]Define functions(positional argument, keyword argument, *args, **kwargs, /, *) (0) | 2020.10.08 |