문제접근
1.
첫번째 접근
•
위의 사진처럼 f(n)은 f(n-1)에서 2 * 1타일만 하나 더 붙은 형태와 f(n-2)에서 1*2타일 2개 붙은 형태와 2*2타일 하나 더 붙은 형태라는 것을 알 수 있음
•
점화식
//pseudo code
cin >> n;
dp[1] = 1
dp[2] = 3
while ( <= n)
dp[i] = (dp[i-1] % 10007 + dp[i-2]*2%10007)%10007
cout << dp[n]
C++
복사
놓쳤던 부분
코드
2016 KB
0 ms
#include <iostream>
#include <vector>
int n;
std::vector<int> dp;
void input_setting()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
std::cin >> n;
dp.resize(n + 1);
}
void solution()
{
int i;
i = 2;
dp[1] = 1;
dp[2] = 3;
while (++i <= n)
dp[i] = (dp[i - 1] % 10007 + dp[i - 2] * 2 % 10007) % 10007;
std::cout << dp[n] << "\n";
}
int main(void)
{
input_setting();
input();
solution();
return (0);
}
C++
복사
