[C++] 백준 11727번 2xn 타일링 2

다이나믹 프로그래밍 문제.

처음에 이 문제를 풀 때 점화식을 잘못잡아서 계속 답이 이상하게 나왔었다.

그래서 어떤 방식으로 푸는지 구글링의 도움을 좀 받았는데, 역시 점화식을 구해서 푸는 방식이였다.

이런 문제 유형도 있음을 알아두어야 될 것 같다.

 

문제 접근 방법

먼저 An을 구할 때, A(n-1)에서 한 칸만 더 추가되는 방식이다.

이 때 2x1이 추가되는 것과 마찬가지 이다. 따라서

• A(n-1)에서 2x1을 추가한 것
• A(n-2)에서는

1. 2 x 1 두개 추가한 것 : 그러나 이 방식은 A(n-1)에서 2x1을 추가한 것에 포함되어 있다.
2. 1 x 2 두개 추가한 것
3. 2 x 2 추가한 것

A(n-3)부터는 어차피 이미 다 포함되어 있으므로 생각할 필요가 없다.

따라서 점화식은

An = A(n-1) + 2 * A(n-2)

가 된다.

 

문제풀이

 

코드 전문

코드가 길지 않으므로 바로 설명하겠다.

이 때, dp값을 저장할 첫번째 1과 두번째 2는 처음에 초기화를 해준다.

그리고 입력받은 n값을 업데이트할 때까지 위에서 구한 점화식

An = A(n-1) + 2 * A(n-2)으로 Bottom Up 방식으로 구해준다.

 

이런 도형 문제가 나오면 실버 문제여도 어려운 것 같다.

DP는 진짜 풀이를 보면 왜 이생각을 못했을까 싶다.

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인 가능하다.