acmicpc.net 1912(DP), 2293(DP), 2294(DP), 2156(DP)

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

기초적인 dp문제.

# -*- encoding: cp949 -*-
n = input()
num = map(int,raw_input().split())
dp = num[:]
dp[0] = num[0]
for i in xrange(1,n):
    dp[i] = max(dp[i], dp[i-1] + num[i])
print max(dp)

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

일반적인 dp문제중 하나. 

# -*- encoding: cp949 -*-
n,k = map(int,raw_input().split())
coin = [0] + [input()for i in xrange(n)]
dp = [0 for i in xrange(101)]
dp[0] = 1
for i in xrange(1,n+1): #모든 동전을 돌아가면서
    for j in xrange(1,k+1): #1원~만들고자하는 k원까지
        if j>=coin[i]: #현재 동전으로 j원을 만들수있으면
            dp[j] += dp[j-coin[i]] #j원은 j-coin[i]개의 갯수로 만들수있다.
print dp[k]

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

위 문제에서 조금 변형된 문제.

# -*- encoding: cp949 -*-
INF = 999999999999
n,k = map(int,raw_input().split())
coin = [0] + [input()for i in xrange(n)]
dp = [INF for i in xrange(10010)]
for i in xrange(1,n+1): #동전 하나하나 돌아가면서
    if coin[i] <= k: #만들려는 돈 k보다 작으면 dp[]에 1개로만들수있다고 저장해둔다.
        dp[coin[i]] = 1

for i in xrange(1,n+1):
    for j in xrange(1,k+1):
        if j>=coin[i]:
            dp[j] = min(dp[j], dp[j-coin[i]]+1) #원래있던 dp값과 j-coin[i]번째동전+1한것의 최소값.
print dp[k] if dp[k]!=INF else -1

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

포도주 시식 문제.

# -*- encoding: cp949 -*-
n=input()
wine = [input() for i in xrange(n)]
dp = [0 for i in xrange(10002)]
if n==1:
    print wine[0]
else:
    dp[0] = wine[0]
    dp[1] = wine[0]+wine[1]
    for i in xrange(2,n):
        dp[i] = max(dp[i-3] + wine[i-1] + wine[i], dp[i-2] + wine[i], dp[i-1])
    print dp[n-1]