[Silver III] 악수 - 8394 (python)

문제 링크

성능 요약

메모리: 187368 KB, 시간: 208 ms

분류

다이나믹 프로그래밍, 수학

제출 일자

2024년 6월 21일 12:09:23

문제 설명

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

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

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

입력

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

출력

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

 

 

코드

 

n = int(input())
dp = [0]*(n+1)
dp[1], dp[2] = 1, 2

if n < 3:
    print(dp[n])
else:
    for i in range(3, n+1):
        dp[i] = (dp[i-1]+dp[i-2])%10
    print(dp[n])

 

전형적인 DP문제였음에도 처음에는 틀렸는데 

이에 10,000,000 범위가 크기에 메모리와 시간을 다시 한번 고려해볼 수 있는 문제였다.