백준[ 8394 | Python ] 악수

문제

https://www.acmicpc.net/problem/8394

풀이

1명에서 악수를 할 수 있는 경우는 없다.
2명에서 악수를 하는 경우는 둘이서 하는 경우와 아예 하지 않는 경우 총 2가지가 있다.
따라서 만들어 놓은 dp테이블에 1, 2를 미리 초기화해주고 점화식에 따라 코드를 짰다.
전형적인 DP문제였다.

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

생각 & 정리

위에서 “전형적인 DP문제 였다.” 라고 한 것 치고는 순열, 조합 문제인 줄 알고
조금 헤맸었다. 더 작은 예로 생각했을 때 규칙성이 보여서 해결했는데, 이번엔 메모리가 문제였다.
분명 코드는 맞는 것 같은데 어떻게 해결해야할까 한참을 고민하다가 수의 크기가 문제일 것이라고 생각되어 해결했다.
메모리 관리, 시간 관리에 새로운 방법을 떠올리게 해주는 문제였다.