[Silver III] 악수 - 8394

문제 링크

성능 요약

메모리: 266116 KB, 시간: 640 ms

분류

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

제출 일자

2025년 6월 29일 22:40:39

문제 설명

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

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

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

입력

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

출력

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

---

💡 해결 방법

💻 코드

# https://www.acmicpc.net/problem/8394
 
 
n = int(input())
 
 
 
way = [1, 1, 2, 3, 5]
pre = way[-1]
#4 > 4
#5 > (3) + (5)= 8
# 6 >  
# 7 > 
 
 
if n < len(way):
    print((way[n]) % 10)
    exit()
 
else:
    for x in range(5, n + 1):
        pre = (way[-1] + way[-2]) % 10
        way.append(pre)
        
               
print((way[-1]) % 10)