알고리즘
[알고리즘 문제해결전략] TILING2 - 타일
[생각의 흐름] 1. 타일을 채우는 방법은 2개이다. 1) 세로로 채우는 방법 2) 가로로 채우는 방법 -> 결국 4X4타일이 됨 2. 타일을 n번째 까지 채웠을 때 그 이후 n+1 타일 부터 채우는 경우의 수를 개싱할 수 있다. #include #include const int MOD = 1000000007; const int MAX_TILE_SIZE = 111; int N; int cache[MAX_TILE_SIZE]; int sol(int n) { if(n == N) return 1; if(n > N) return 0; int &ret = cache[n]; if(ret != -1) return ret; // 타일을 세로로 쓰는 경우 + 타일을 가로로 2개 쓰는 경우 ret = (sol(n+1) % ..
