[백준 8394번] 악수 (C++)

문제링크 : https://www.acmicpc.net/problem/8394

8394번: 악수

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N;
int dp[10000001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;

    dp[0]=1;
    dp[1]=2;

    for(int i=2; i<N; i++)
    {
        dp[i] = (dp[i-1] + dp[i-2]) % 10; //피보차니 수열 (마지막 한자리만)
    }

    cout << dp[N-1];

    return 0;
}

 

직접 경우의 수를 적어보면 피보나치 수열의 점화식을 따른다는 것을 알 수 있다.

여기서 추가적으로 해주어야 할 것은 마지막 자리만 출력한다는 것이다.

따라서 점화식에 %10을 하여 10으로 나눈 나머지만 저장하도록 해준다.