Approach
잘 생각해보면, 해당 사람이 악수를 할 수 있는지 여부는 앞의 사람이 악수를 했는지 여부와 관련이 있다
dp[i][0] : i번째 사람까지 참석했다고 했을 때의 경우의 수 중 i번째 사람이 앞 사람과 악수를 하지 않는 경우
dp[i][1] : i번째 사람까지 참석했다고 했을 때의 경우의 수 중 i번째 사람이 앞 사람과 악수를 하는 경우
dp[i][0] = dp[i - 1][0] + dp[i - 1][1] (악수를 하지 않으므로, 앞에 있는 사람이 악수를 했는지 안했는지 여부가 중요하지 않음)
dp[i][1] = dp[i - 1][0] (앞 사람과 악수를 해야하므로, 앞에 있는 사람이 무조건 악수를 하면 안된다.)
Code
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
int dp[10000001][2]; // 0 : front non connected, 1: front connected
int main(void){
fastio;
dp[2][0] = 1;
dp[2][1] = 1;
int n;
cin >> n;
for(int i = 3; i <= n; i++){
dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % 10;
dp[i][1] = (dp[i - 1][0]) % 10;
}
cout << (dp[n][0] + dp[n][1]) % 10 << "\n";
return 0;
}