문제설명
풀이
사자를 배치하는 경우의 수를 구할 때, 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다면, N이 1일 때부터 4일 때까지 각각 3,7,17,41 가지의 경우의 수가 나온다.
이때 규칙을 찾아보면 N의 값은 (N-1의 경우의 수) * 2 + (N-2의 경우의 수)라는 규칙이 생기는 것을 알 수 있다.
위 규칙으로 점화식을 세운다면 dp[N]=dp[N-1]*2 + dp[N-2]이 나온다.
이렇게 구해진 점화식을 이용하여 답을 구했다.
코드
#include <iostream>
using namespace std;
int dp[100001];
int main()
{
int num;
dp[0] = 1;
dp[1] = 3;
dp[2] = 7;
cin >> num;
for (int i =3; i <=num; i++)
{
dp[i] = ( (dp[i-1] * 2) + dp[i-2] ) % 9901;
}
cout << dp[num];
}