메모이제이션

[baekjoon 11726] 2xN 타일링- DP(동적 프로그래밍) (C++)

www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 기본 유형의 DP 문제이다. DP는 수학적인 접근이 필요해서 연습이 많이 필요한 것 같다. 또한, 주어진 문제를 작은 문제로 나눠서 푼 뒤, 결과를 통해 문제를 해결하는 것은 분할 정복과 비슷하다. 하지만 분할 정복은 문제를 분할 시 겹치는 문제가 발생하지 않지만 DP는 겹치는 문제들이 발생한다. 따라서 보통 메모이제이션을 이용해서 같은 문제에 대한 결과가 나오는 함수의 호출을 줄여준다. #include using namespace..