14651

날짜 : 2022. 11. 06

사용 언어 : python

 

문제

 

 

코드

import sys

n = int(sys.stdin.readline())
num = [0] * 33334
num[1] = 0
num[2] = 2

for i in range(3, len(num)):
    num[i] = num[i-1] * 3

print(num[n] % (10**9 + 9))

 

 

알게된 점

- 숫자가 기하급수적으로 커져서 머리를 쥐어짰는데 결국은 해당 값의 점화식을 이용해서 푸는 문제였다;;

- 0 -> 2 -> 6 -> 18 ... 이렇게 증가하기 때문에 n이 3보다 큰 경우에 a[n] = 3 * a[n-1]이라는 식이 도출된다.

 

 

참고 사이트

-