[Python/BOJ] 14651. 걷다보니 신천역 삼 (Large)

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

14651번: 걷다보니 신천역 삼 (Large)

문제

욱제는 ‘삼’이란 음절을 참 좋아한다. 인삼, 홍삼, 해삼, 삼성, 이춘삼(李春森), 삼식이, 삼시세끼, ㄴㄴ 그거 안 삼, 삼과 죽음, 알았삼, 걷다보니 신천역 삼, 그리고 특히 일이삼을 좋아한다. 그래서 욱제는 3을 가지고 놀아보기로 했삼.

3개 숫자(0, 1, 2)만 가지고 N자리 3의 배수를 만들어 보삼. 만드는 배수는 자연수 이삼. 0으로 시작하는 수는 만들 수 없는 수 이삼. 3의 배수가 몇 개나 나올 수 있삼?

입력

N을 입력 받으삼 (1 ≤ N ≤ 33,333)

출력

0, 1, 2만 가지고 만들 수 있는 N자리 3의 배수의 개수를 출력하삼. 숫자가 너무 커질 수 있으니까 답을 109+9(1,000,000,009)로 나눈 나머지를 출력하삼.

풀이

Code(시간초과)

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def check(num, count) :
    global ans
    # 1. 종료 조건 설정
    if count == n :
        if int(num) % 3 == 0 : ans += 1
        return
    # 2. for
    if count == 0 :
        for i in ['1', '2'] :
            check(num + i, count + 1)
    else :
        for i in ['0', '1', '2'] :
            check(num + i, count + 1)

n = int(input())
ans = 0
check('', 0)
print(ans)

Code

import sys
input = sys.stdin.readline

n = int(input())
# 1. dp 생성
dp = [0] * (n+1)
if n > 1 :
    # 2. dp 초기값 설정
    dp[2] = 2
    # 3.
    for i in range(3, n+1) :
        # 3-1. 점화식에 따라 처리
        dp[i] = (dp[i-1] * 3) % 1000000009
# 4. 결과 출력
print(dp[n])