Baekjoon 11727 2xn 타일링 2 JAVA

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

11727번: 2×n 타일링 2

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%2011727

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

 

해당 문제는 Baekjoon 11726 2xn 타일링 업그레이드 문제다

https://blog.naver.com/soonil0119/222497179409

Baekjoon 11726 2xn 타일링 JAVA

기존은 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] 이 된다.