https://www.acmicpc.net/problem/8394
dp(i): i번째 사람까지 악수하는 경우의 수
라고 정의할 때, 앞 사람과 악수하는지 여부로 경우를 나눌 수 있다.
dp(i) = dp(i, 0) + dp(i, 1)
이때, 아래와 같이 점화식을 정의할 수 있다.
그리고 i = 1일 때, 경우의 수는 다음과 같다.
dp(1, 0) = 1
dp(1, 1) = 0
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
vector<vector<int>> dp(n+1, vector<int>(2,0));
dp[1][0] = 1;
dp[1][1] = 0;
for(int i=2; i<=n; i++){
dp[i][0] = dp[i-1][0] + dp[i-1][1];
dp[i][1] = dp[i-1][0];
}
cout << dp[n][0] + dp[n][1];
return 0;
}
#include <iostream>
using namespace std;
int dp[10000001][2];
int main()
{
int n;
cin >> n;
dp[1][0] = 1;
for(int i=2; i<=n; i++){
dp[i][0] = (dp[i-1][0] + dp[i-1][1]) % 10;
dp[i][1] = dp[i-1][0];
}
cout << (dp[n][0] + dp[n][1]) % 10;
return 0;
}