11726번

#include<iostream>
using namespace std;
int main() {
	int dp[1001];
	int n;
	cin >> n;
	dp[0] = 0;
	dp[1] = 1;
	dp[2] = 2;
	for (int i = 3; i <= n; i++)
	{
		dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
	}
	cout << dp[n];
}

 

이 문제또한 dp문제 이기때문에 작은 문제를 해결한 다음 그 문제를 기반으로 큰문제까지 해결해야한다.

먼저 타일이 0개 일땐 방법이 0개이다. 1개면 1개 2개면 총 2개

3개부터는 점화식을 활용하여 구할수 있다.

dp[i] = 이전 수의 방법갯수 + 이전의 이전수의 방법갯수;

 

마지막 말고 각 계산에서 10007로 나눈후 나머지를 대입하는 이유

저장할 수 있는 수의 범위가 없다면 마지막이 아닌 중간에 %10007을 하는 것과 마지막에 %10007을 하는 것의 결과가 똑같음을 증명할 수 있습니다. 여기서는 수가 int 범위까지만 갈 수 있기 때문에 중간에 %10007을 안 하면 오히려 잘못된 값으로 오버플로우하게 됩니다.

 

test

#include<iostream>
using namespace std;
int main() {
	long long a = 12453424;
	long long b = 12312134;
	int temp = (a % 10007) + (b % 10007);
	int temp2 = (a + b) % 10007;
	cout << temp << " " << temp2;
}

위 테스트 결과를 보면 temp와 temp2의 값이 같은것을 볼 수 있습니다.