기록공간

동적계획법을 사용하는 문제이다. 2x1 크기부터 타일을 채울 수 있는 방법의 수를 그려보면 다음과 같은 결과가 나온다. 2x1 => 1개 2x2 => 2개 2x3 => 3개 2x4 => 5개 ..... 규칙을 보면 피보나치와 같다. F[i] = F[i - 2] + F[i - 1] 하지만 2x1000까지 방법의 수는 int로 표현할 수 없으며 10007를 나눈 나머지를 출력하라고 하였기 때문에 방법의 수를 10007로 나눈 값을 dp 테이블에 기록하면 된다. 코드는 다음과 같다. #include using namespace std; int main() { int dp[1000 + 1]; int input; cin >> input; dp[0] = 0; dp[1] = 1; dp[2] = 2; for (int ..