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