[백준 8394번] [동적 계획법] 약수

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;
}