poly

[알고리즘 문제해결전략] POLY - 폴리오미노

[생각의 흐름] 1. 위에서 아래로 정사각형을 x개씩 채워나간다. 2. 직전 윗칸에서 채운(사용한) 사각형의 갯수와 현재 칸에 채우려는 사각형의 갯수를 알면 경우의 수를 구할 수 있다. ( 윗칸에서 채운 사각형의 수 + 현재 칸을 채우려는 사각형의 수 - 1) 3. 재귀함수를 통해 모든 경우의 수를 구한다. 4. 직전 윗칸에서 채운(사용한) 사각형의 갯수와 현재 사용할 수 있는 남은 사각형(leftBlock)의 갯수를 통해 메모이제이션이 가능하다. /* https://www.algospot.com/judge/problem/read/POLY */ #include #include const int MAX_BLOCK = 101; const int MOD = 10000000; int cache[MAX_BLOCK..