-
https://www.acmicpc.net/problem/11727
https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%2011727
해당 문제는 Baekjoon 11726 2xn 타일링 업그레이드 문제다
https://blog.naver.com/soonil0119/222497179409
기존은 2x1, 1x2 로만 채웠다면 해당 문제는 2x2 타일까지 추가된 문제다.
해당 문제도 dp로 풀기 위해 처음 5까지의 경우를 직접 그려보았다.
1 3 5 11 21이라는 경우의 수가 나왔는데
직접 그려서 보게 된다면 아래와 같은 그림인데
n = 3 일 때를 보면 n = 1일 때에다가 2x1 타일 두 개를 붙인 것과, 2x2 타일을 하나 붙인 것에다가
n = 2 일 때에다가 1x2 타일을 붙인 것이 된다.
처음에는 식을 막 이것저것 다 생각해 보았는데 최종 dp 식은
dp[i] = dp[i-2]*2 + dp[i-1] 이 된다.
728x90'알고리즘 > Baekjoon' 카테고리의 다른 글
Baekjoon 10974 모든 순열 JAVA (0) 2021.11.11 Baekjoon 14621 나만 안되는 연애 JAVA (0) 2021.11.11 Baekjoon 9461 파도반 수열 JAVA (0) 2021.11.11 Baekjoon 2178 미로 탐색 JAVA (0) 2021.11.11 Baekjoon 18870 좌표 압축 JAVA (0) 2021.11.11 댓글