[백준] 알고리즘 8394번 - 악수 문제

문제

www.acmicpc.net/problem/8394

8394번: 악수

소스코드

#include <bits/stdc++.h>
using namespace std;
long long dp[10000001];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n,ans=0;
	cin >> n;
	dp[1] = 1, dp[2] = 2;
	for (int i = 3; i <= n; i++) {
		dp[i] = (dp[i - 1] + dp[i - 2])%10;
	}
	
	cout << dp[n];
}

풀이

간단하게 피보나치로 해결할 수 있다.

1. 아무랑도 안하는 경우

2. 1,2 랑하는 경우

3. 2,3 이랑하는 경우

 

즉 2가 동시에 1,3이랑 악수를 할 수 없다.