acmicpc.net 9461(DP), 10844(DP), 2133(DP), 5430(덱)

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

# -*- encoding: cp949 -*-
dp = [0 for i in xrange(150)]
dp[1]=1
dp[2]=1
dp[3]=1
dp[4]=2
dp[5]=2
for i in xrange(6,101):
    dp[i] = dp[i-1] + dp[i-5]
for t in xrange(input()):
    n=input()
    print dp[n]

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

# -*- encoding: cp949 -*-
dp=[[0 for j in xrange(10)] for i in xrange(102)]
n=input()
for i in xrange(10):
    dp[1][i] = 1
for i in xrange(2,n+1):
    for j in xrange(10):
        if j==0:
            dp[i][j] = dp[i-1][1]%1000000000
        elif j==9:
            dp[i][j] = dp[i-1][8]%1000000000
        else:
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1])%1000000000

s = 0
for i in xrange(1,10):
    s = (s+dp[n][i])%1000000000
print s

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

# -*- encoding: cp949 -*-
n=input()
dp = [0 for i in xrange(31)]
dp[0] = 1
dp[2] = 3
for i in xrange(4,31):
    dp[i] = dp[i-2]*3
    for j in xrange(4,i+1,2):
        dp[i] += 2*dp[i-j]
print dp[n]

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

아래는 시간초과의 벽을 못넘고 실패한 코드다. 채점현황을 보면 파이썬의 덱 라이브러리를 써서는

못푸는 듯 싶다. 덱 참고용으로 시간초과난 코드지만 올려둔다. 

https://docs.python.org/2/library/collections.html

C++의 덱으로 바꾸면 통과한다.

# -*- encoding: cp949 -*-
from collections import deque
import sys
for t in xrange(int(sys.stdin.readline())):
    d = deque()
    p=sys.stdin.readline()
    sys.stdin.readline()
    d.extend(eval(sys.stdin.readline()))
    e_flag = False
    for c in p:
        if c=='R':
            d = deque(reversed(d))
        elif c=='D':
            if len(d)==0 or d[0]=='':
                sys.stdout.write('error\n')
                e_flag = True
                break
            d.popleft()
    if not e_flag:
        sys.stdout.write('['+','.join(map(str,d))+']\n')