경우의 수와 확률,타일링 방법의 수 세기

동적계획법 -> 최적화

But, 경우의 수 문제에도 사용

경우의 수 문제는 값이 지수적으로 증가하기 때문에 

오버플로에 유의해야 한다.

예제 : 타일링 방법의 수 세기 - 2xn 크기의 사각형을 2x1 크기의 타일로 채우는 방법의 수를 계산하는 문제 1. 완전탐색  2. 메모이제이션 <2xn>을 이루는 2가지 방법

#include "stdafx.h"

#include <iostream>

using namespace std;

int mod = 1000000007;

int cache[101];

int tiling(int width) {

if (width <= 1)

return 1;

//기저 사례

int& ret = cache[width];

if (ret != -1)

return ret;

//메모이제이션

return ret = (tiling(width - 1) + tiling(width - 2)) % mod;

}

int main() {

memset(cache, -1, sizeof(cache));

int testcase,width;

cin >> testcase;

for (int i = 0; i < testcase; i++) {

cout << "width 는 ? : ";

cin >> width;

cout << tiling(width) << endl;

}

}