acmicpc.net 11726(DP), 11727(DP), 11052(DP)

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

피보나치 수열 문제처럼 동적 프로그래밍으로 풀면 된다.

2*1이면 1개, 2*2면 2개, 2*3 = 2*1개 + 2*2개, 2*n = 2*(n-1)+2*(n-2) 이다.

# -*- encoding: cp949 -*-
n = int(raw_input())
tile = [0 for i in range(1001)]
tile[0] = -1
tile[1] = 1
tile[2] = 2
for i in xrange(3,n+1):
    tile[i] = (tile[i-1] + tile[i-2])%10007
print tile[n]

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

11726이랑 거의 똑같다. 위 코드 중간에 식만 tile[i] = (tile[i-1] + 2*tile[i-2])%10007 로 바꿔주면된다

또 dp[2] = 3이다.

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

붕어빵이 n개라고 가정하면.. 

1. 배열[0] 인덱스에 1개씩 팔았을때의 최대값을 저장해둔다.

2. 배열[n] 인덱스에 [(1개씩 팔았을때값),(n-1개 팔았을때 최대값+1개씩 팔았을때),(n-2개 팔았을때 최대값+1개씩 팔았을때)] 등등을 다 돌아가며 계산한다.

3. 최대값이 나오면 값을 교환해준다.

아래 주석되있는거 다 풀고 돌면서 이해해보자.

bread배열이 n개 팔았을때의 최대값을 저장해뒀고, p배열에 1개씩 팔았을때의 값을 입력해뒀다.

n = int(raw_input())
price = map(int,raw_input().split())
max_price = [0 for i in range(n)]
max_price[0] = price[0]
for i in range(1,n):
    max_price[i] = price[i]
    for j in range(i):
        #print 'bread[{}] = (bread[{}] + p[{}])'.format(i,i-j,j)
        if max_price[i] < max_price[i-j-1] + price[j]:
            max_price[i] = max_price[i-j-1] + price[j]
print max_price[n-1]