Algorithm/acmicpc.net
다이나믹 프로그래밍2
winney916
2021. 12. 9. 18:16
728x90
내가 생각하는 다이나믹 프로그래밍의 핵심은 점화식을 파악하는데 있다. 그러니까 고등학교 때 봤던 확률과 통계 느낌 나는 문제들을 이해하는게 아주 중요하다.
#11726번 2xn 타일링 https://www.acmicpc.net/problem/11726
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
n의 변화에 따른 타일링의 경우의 수를 계산해주면 되는데 내가 처음 판단한 점화식은 이렇다.
An = An-1 + (n-2) 였다.
뭐 예상한 결과다.
고민고민 하다가 결국엔 서치...
결론은 An = An-1 + An-2 였고
맞추긴 했다.
그런데 뭔가 찝찝한 이 기분..
점화식 못 찾으면 어떻게 풀지..?