acmicpc.net 9465(DP), 2096(DP), 1904(DP), 11586, 1225

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

스티커를 하나 고르면 예시를 보고 대충 파악할수 있겠지만 다음 스티커는 대각선으로 골라야 한다.

그리고 예시에 나와있듯이 max(위에서 시작하는 대각선, 아래에서 시작하는 대각선) 은 답이 아니다.

max(한칸전 대각선+현재 값, 두칸전 대각선+마지막 4칸중에서의 최대값) 이 답이다. 

# -*- encoding: cp949 -*-
for t in xrange(int(raw_input())):
    dp = [[0 for j in xrange(100001)] for i in xrange(2)]
    n = int(raw_input())
    st = [map(int,raw_input().split()) for i in xrange(2)]
    dp[0][1] = st[0][0]; dp[1][1] = st[1][0]
    for i in xrange(2,n+1):
        dp[0][i] = max(dp[1][i-1], dp[1][i-2]) + st[0][i-1]
        dp[1][i] = max(dp[0][i-1], dp[0][i-2]) + st[1][i-1]
    print max(dp[0][n], dp[1][n])

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

쉬운 dp문제.

# -*- encoding: cp949 -*-
n = int(raw_input())
num = [map(int,raw_input().split()) for i in xrange(n)] #숫자를 입력받는다.

for k in xrange(2): #k==0일땐 max, k==1일땐 min.
    func = lambda *a: max(*a) if k==0 else min(*a) #k==0일땐 max로, k==1일땐 min으로 동작하는 함수를 만든다.
    dp = [[0 for j in xrange(3)] for i in xrange(2)] #dp 테이블 0으로 초기화되어있다.
    for i in xrange(n): 
        dp[1][0] = func(dp[0][0], dp[0][1])+num[i][0] #dp값 계산.
        dp[1][2] = func(dp[0][1], dp[0][2])+num[i][2]
        dp[1][1] = func(dp[0][0], dp[0][1], dp[0][2])+num[i][1]
        for j in xrange(3): #효율적인 메모리사용을 위해 dp[1]에 저장되어있던 값들을 dp[0]으로 할당해준다. 이걸로 다시 시작.
            dp[0][j] = dp[1][j]
    print func(dp[1]),

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

1번째 : 1

2번째 : 00 11

3번째 : 001 100 111

4번째 : 0011 0000 1001 1100 1111

N번째 : N-2번째에 00을 붙여 만든거 + N-1번째에 1을 붙여 만든거. (위의 파랑색과 빨간색 참조)

# -*- encoding: cp949 -*-
dp = [0 for i in xrange(1000000)]
dp[1] = 1
dp[2] = 2
n = int(raw_input())
for i in xrange(3,n+1):
    dp[i] = (dp[i-2]+dp[i-1])%15746
print dp[n]

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

# -*- encoding: cp949 -*-
n = int(raw_input())
mirror = [raw_input() for i in xrange(n)]
k = int(raw_input())
if k==1:
    print '\n'.join(mirror)
elif k==2:
    for i in xrange(n):
        print mirror[i][::-1]
elif k==3:
    for i in xrange(n-1,-1,-1):
        print mirror[i]

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

# -*- encoding: cp949 -*-
a,b = map(lambda x:map(int,x), raw_input().split())
print sum([sum([i*j for i in a]) for j in b])