8394 악수

사람들이 일렬로 앉아있을 때, 양 옆사람 끼리 악수를 할 수 있다고 한다. 이 때 가능한 모든 경우의 수를 계산하는 문제이다. 모든 사람이 악수를 안하는것도 계산해야 한다.

패턴을 살펴보면 피보나치 수열이 나오는것을 알 수 있다. 따라서 피보나치 수열을 구현해주면 되는데, 숫자가 매우 커지기 때문에 10 으로 나눈 나머지를 구해야 한다. 피보나치를 구하면서 swap 을 한 후에 10으로 나머지연산을 해주면 된다.

소스