백준 8394 악수

처음에는 규칙을 찾아보려 했지만... dp로 풀 수 있다.
d[n] 을 사람의 수가 n명일 때, 악수를 하는 방법의 수
라고 하면
d[n]은 맨 끝의 사람이 악수를 하는 경우와 안 하는 경우로 나눌 수 있다.
악수를 하는 경우는 d[n - 2]가지 경우의 수가 있을 것이고,
악수를 하지 않는 경우는 d[n - 1]가지의 경우의 수가 있을 것이다.
d[n] = d[n - 1] + d[n - 2]가 된다.