문제

회의가 끝났고, 이제 악수를 하는 시간이다. 모든 사람은 직사각형 탁자 하나의 한 면에 앉아있다.

자리를 벗어나지 않고 악수를 하는 방법의 수는 총 몇 가지일까?

각 사람들은 자신의 왼쪽이나 오른쪽에 있는 사람들과 악수를 할 수 있다. (안 할 수도 있다)

입력

첫째 줄에 회의에 참석한 사람의 수 n (1 ≤ n ≤ 10,000,000)이 주어진다.

출력

첫째 줄에 악수를 하는 방법의 수를 출력한다. 수가 매우 커질 수 있기 때문에, 마지막 자리만 출력한다.

힌트

n=4인 경우에는 5가지 방법이 있다.

다이내믹 프로그래밍 문제다. 규칙을 찾아 점화식을 세우는 게 먼저다.

n=1이면 1(악수를 안 하는 경우), n=2면 2(악수를 안 하는 경우, 둘이 악수하는 경우)다.

n=3은?

1. 세 번째 사람이 악수를 안 할 경우

   이 때는 두 명이 있을 경우와 같다. 즉 DP_i-1이다.

2. 세 번째 사람이 악수를 할 경우

   그럼 첫 번째 사람 혼자 남는다. 즉 DP_i-2의 경우와 같다.

따라서 DP_n = DP_i-1 + DP_i-2다.

써놓고 보니, 많이 본 공식이다. n번째 숫자는 n-1과 n-2의 합. 그렇다. 피보나치 수열이다.

회의에 n명이 참석했을 때 악수할 수 있는 경우의 수는 fibo(n)이다.

여기선 마지막 자리만 출력하라고 하니, 피보나치 수를 구하면서 마지막 자리만 계산해 넣으면 된다.

처음엔 피보나치 수인 걸 눈치 못 채고, 다이내믹 프로그래밍 점화식대로 우직하게 풀었다. 몇 번 수정한 끝에 시간 초과도 피했다. 리스트(dp)에 값을 넣어줄 때 끝자리를 미리 구해 넣어주는 것이 시간 초과를 피하는 방법이다. (5번째 줄 참고)

n = int(input())
dp = [1] * n
dp[1] = 2
for i in range(2, n):
    dp[i] = (dp[i-1]%10 + dp[i-2]%10)%10
print(dp[-1])

이를 피보나치 수를 구하는 식으로 바꾸면 훨씬 간단해진다.

n, m = 1, 1 # 첫 번째와 두 번째 숫자를 미리 지정
for _ in range(int(input())):
    n, m = m, (n+m)%10
print(n)

간단하고 깔끔하다. :)

[문제 보기]