acmicpc.net 6359(DP), 1309(DP), 1149(DP)

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

카테고리 분류는 dp인데 그냥 풀면 된다.

# -*- encoding: cp949 -*-
arr = [0]*101
t = int(raw_input())

for i in xrange(t):
    n = int(raw_input())
    for j in xrange(1,n+1): #각 방을 돌면서
        count = 1
        for k in xrange(2,j+1): #상범이가 한번씩 왔다갔다하는거 계산
            if j%k==0:
                count += 1
        arr[j] = count #arr에 몇번 열고 닫는지 저장해둔다.
    inmate = 0
    for j in xrange(1,n+1): #모든 방을 돌면서
        if arr[j]%2==1: #홀수번이면 탈출할수 있다.(짝수번이면 닫힌문)
            inmate += 1
    print inmate

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

11727번 타일채우기 문제랑 비슷하다.

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

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

현재 R집일때의 최소값은 이전 집의 (G,B까지의 값중 최소값) + 현재 R의 값이다.

G,B도 하나하나 구해줘야 한다. 이웃만 색깔이 다르면 되기 때문에 이런식으로 구하면 된다.

# -*- encoding: cp949 -*-
dp = [[0,0,0] for i in xrange(1001)]
n = int(raw_input())
color = [[0,0,0]]+[map(int,raw_input().split()) for i in xrange(n)] #입력받는다.

for i in xrange(1,n+1):
    dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + color[i][0] #R의 최소 값은 (이전 집의 g,b까지의 값중 최소값) + 현재 r의 값. 
    dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + color[i][1] #G ~~~~~~ 이전 집의 r,b~~~~ +현재 g의 값.
    dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + color[i][2] #B

print min(dp[n][0],dp[n][1],dp[n][2])