8394.md

백준 8394번 악수

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

---

코드 설명

• n이 1일때와 2일때는 쉽게 1, 2로 구할 수 있다.
• 다음으로 n이 3일때와 4일때를 보면 규칙을 한가지 발견할 수 있는데 n이 3일때에는 n이 1일때와 n이 2일때를 더한 합과 같다는 것이다.
• 이를 바탕으로 점화식을 만들 수 있다. -> dp[n] = dp[n-1] + dp[n-2]

소스코드

• 메모리 : 117864 KB
• 시간 : 2928 ms

n = int(input())
dp = [0 for i in range(n+1)]
dp[1], dp[2] = 1, 2

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

오답 노트

• 문제를 제대로 안 읽고 출력형식에 따르지 않았기 때문에 메모리 초과가 나왔다.
• 문제에는 마지막 자리 수만 출력하라고 나와있다.

오답 코드

n = int(input())
dp = [0 for i in range(n+1)]
dp[1], dp[2] = 1, 2

for i in range(3, n+1):
    dp[i] = dp[i-1] + dp[i-2]
    
print(dp[n])