Awesome

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

예시를 그대로 갖고왔다.

5번째 계단은 무조건 밟아야 한다.

그럴 때 최댓값은, 5번째 계단의 점수 20을 더한 상태에서 

4번째 계단을 선택했을때이거나

3번째 계단을 선택했을 때이다.

4번째 계단을 선택하려면 3번째 계단은 선택하면 안 된다. (3개 연속 밟을 수는 없으므로)

3번째 계단을 선택하려면 2, 1번째 계단 중 어떤 것을 선택해도 상관 없으며 최댓값을 고르면 된다. 

val은 바로 전 계단을 선택했을 때의 최댓값을 R, 

전전 계단을 선택했을 때의 최댓값을 F로 해서 두 값을 모두 담았다. 나중에 최종적으로 둘 중에 최댓값을 고를 것이다.

이를 정리해보면

N번째 계단에서의 최댓값은 일단 N번째 점수를 더한 상태에서 (stair[col])

N-1번째를 선택하되 N-1은 바로 전 계단이 아닌 전전 계단을 선택한 상태거나 (val[col-1][F])

N-2번째를 선택하고 N-2가 바로 전 계단을 선택했거나, 전전 계단을 선택했을때의 두 점수 중에서 최댓값을 고르는 것이다. (max(val[col-2][F], val[col-2][R])

쉽게 설명하면 F는 Front로 "앞에꺼, 즉 -2번째 계단을 선택한 상태" , R은 "뒤에꺼, 즉 -1번째 계단을 선택한 상태"로 보면 된다.

내가 풀었지만, F, R이라는 단어를 잘못 선택한 것인지 쉽게 설명하기가 영 어렵다.

그림 그리면서 F는 전전 거를 선택한 상태, R은 전 거를 선택한 상태라고 생각하면 조금이나마 쉽다..

미래의 나에게 하는 이야기.

import sys


def solve():
	dp = []
	dp.append([stair[0], stair[0]])  # dp[0]

	for i in range(1, N):
		if i == 1:
			dp.append([stair[0]+stair[1], stair[1]])
		else:
			walk = dp[i-1][JUMP] + stair[i]
			jump = max(dp[i-2]) + stair[i]
			dp.append([walk, jump])
				
	print(max(dp[N-1]))


WALK, JUMP = 0, 1  # 그 전 계단을 걸어온경우, 점프한경우
input = sys.stdin.readline
N = int(input())

stair = [int(input()) for _ in range(N)]

solve()

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

선행 문제인 RGB거리 문제를 풀었다면 쉽게 해결할 수 있는 문제였다.

추상화가 필요없다는 점에서 이게 더 쉬운 것 같기도...

마찬가지로 이전 행까지의 값을 저장해놓고 있어야 하기 때문에 동적 프로그래밍에 해당하는 문제이다.

bottom-up으로 찾고 싶은 높이까지 최댓값을 각각 열마다 저장해나가는 것이 포인트다.

파이썬이기 때문에 삼각형 모양의 배열 선언이 비교적 쉬웠던 것 같다.

import sys
n = int(sys.stdin.readline())
tri = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
val = [[0]*i for i in range(1, n+1)]

val[0][0] = tri[0][0]

for row in range(1, n):
    if row == 1:
        val[1][0] = tri[1][0] + val[0][0]
        val[1][1] = tri[1][1] + val[0][0]
    for col in range(row+1):
        if col == 0:  # 제일 첫 번째
            val[row][0] = tri[row][0] + val[row-1][0]
        elif col == row:  # 제일 마지막번째
            val[row][-1] = tri[row][-1] + val[row-1][-1]
        else:  # 그게 아닌, 대각선 방향 두 개 중에 선택해야 하는 것들
            val[row][col] = tri[row][col] + max(val[row-1][col-1], val[row-1][col])

print(max(val[n-1]))

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

처음에는 이게 왜 동적 프로그래밍인지 모르겠어서 해결방법이 보이질 않았다.

현재 R을 선택했을 때와 G, B를 선택했을 때의 결과를 각각 따로 저장해야된다고는 생각했는데

막연히 생각하기에 그렇게 하면 시간이 너무 오래 걸릴 것 같았다.

하지만 그렇게 해도 한 번 돌 때마다 3개의 계산을 한꺼번에 하므로, N의 시간밖에 걸리지 않는다는 것.

for문 안쪽의 의미는 다음과 같다.

• i번째에 R 색깔을 칠했을 때의 누적 비용 (0~i-1까지 무언가를 칠하고, i번째에 R을 칠했을 때의 모든 비용) =
• i번째에 R색깔을 칠하는 데 드는 비용 (이번만 칠하는 데 드는 비용) +
• i-1번째에서 G 혹은 B 색깔로 칠하는데 들었던 비용 중 최솟값(이 값 역시 누적된 비용이다)

import sys
N = int(sys.stdin.readline())
cost = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] # 입력(색칠비용)
val = [[0,0,0] for _ in range(N)]  # 계산될 색칠 비용 결과
R = 0
G = 1
B = 2

val[0][R] = cost[0][R]
val[0][G] = cost[0][G]
val[0][B] = cost[0][B]

for i in range(1, N):
    val[i][R] = cost[i][R] + min(val[i-1][G], val[i-1][B])
    val[i][G] = cost[i][G] + min(val[i-1][R], val[i-1][B])
    val[i][B] = cost[i][B] + min(val[i-1][G], val[i-1][R])

print(min(val[N-1][R], val[N-1][G], val[N-1][B]))  # 0부터 시작이므로 N-1

어렵다.

동적 프로그래밍은 점화식을 세우면 풀 수 있다고 했는데,

점화식은 세웠는데 그걸로 어떻게 구현해야할지 재귀에서 한참 헤맸다.

처음이라 그런지, 피보나치만 생각하고 Top-down만 생각했던 게 실수였던 것 같다.

또, 점화식이 D(n) = min(D(n/3), D(n/2), D(n-1)) + 1 이런 식으로 나오다보니 자연스럽게 탑다운만 생각했다.

사실, 탑다운도 가능하고 바텀업도 가능하다.

하지만 실행 시 탑다운 방식은 큰 수를 넣으면 재귀가 너무 깊다고 하면서 오류가 뜬다.

Top-Down (큰 수 오류)

enter = int(input())
m = [-1 for i in range(enter + 1)]  # memoization

def dp(n):
    if n == 1:
        return 0
    if n == 2 or n == 3:
        return 1
    if m[n] != -1:
        return m[n]
    temp1 = dp(n-1) + 1  # -1 했을 때 최소 연산
    temp2 = temp1  # 0으로 하면 안되서 temp1과 같게 해 줌
    temp3 = temp1
    if n % 2 == 0:
        temp2 = dp(n//2) + 1
    if n % 3 == 0:ㅁ
        temp3 = dp(n//3) + 1
    m[n] = min([temp1, temp2, temp3])
    return m[n]

print(dp(enter))

Bottom-Up

n = int(input())
m = []  # 미리 초기화를 하면 밑부분 m[0]~m[3]을 초기화해주는 부분에서 out of index 날 수 있다

m.append(0)
m.append(0)
m.append(1)
m.append(1)

for i in range(4, n+1):
    m.append(m[i-1] + 1);
    if(i % 2 == 0):
        m[i] = min(m[i], m[i//2] + 1) 
    if(i % 3 == 0):
        m[i] = min(m[i], m[i//3] + 1) 

print(m[n])

이 문제에서 생각해내지 못한 것은 10번째 줄이다.

-1 하는 것을 기본으로 놓고,

그 이후에 2나 3으로도 계산해보면서 무엇이 최솟값인지 비교해보는 방식으로 푸는 것이었다.

첫째 줄은 막대기의 길이이다.

둘째 줄은 각 막대기의 가격이다.

한 막대기를 선택해서, 그 막대기를 적절하게 자르든 안 하든, 가장 비싼 가격을 만들어야 한다.

예를 들어 길이 4의 막대기는 2로 나누어서 5+5=10이 최대 가격이 된다.

막대기 n을 선택해 나누려고 하는데,

i를 1부터 시작해서 i : n-i 비율로 나눴다고 생각하자. 

예를 들어 막대기 4를 1:3, 2:2, 3:1, 4:0 비율로 나눌 수 있다. 

이 때 i는 1부터 n까지 모든 경우를 볼 것이기 때문에 더이상 건들지 말고 표 가격 그대로라고 생각하고,

n-i의 가격을 최대 가격이라고 생각하면

i=n까지 계산 및 비교를 끝냈을 때 n의 최대 가격을 알아낼 수 있을 것이다.

4를 1:3으로 나눴다면 1을 기준점으로 삼고 그냥 두고, 3을 막대기 3의 최대 길이라고 생각하자는 것이다.

이것을 점화식으로 나타내면 다음과 같다.

Rn = max(Pi + Rn-i) (i=1~n. R은 최대 가격, P는 표에 주어진 가격)

R1 = max(P1 + R0)

R2 = max(P1 + R1, P2 + R0)

R3 = max(P1 + R2, P2 + R1, P3 + R0)

R4 = max(P1 + R3, P2 + R2, P3 + R1, P4 + R0)

....

계속해서 R0, R1, R2 등의 계산이 반복되고 있기 때문에 동적 프로그래밍으로 풀어갈 수 있다.

다이나믹 프로그래밍은 점화식을 알아내면 풀 수 있다고 한다. 

저 문제를 봤을 때 DP인 것을 인식하고 수식을 생각해낼 수 있을지 솔직히 지금은 자신없지만...