06-6. 다이나믹 프로그래밍 복습

📝문제1. 백준 14501번(퇴사)

- 문제

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

- 코드💻

n = int(input()) 
t = [] 
p = [] 
dp = [0] * (n+1)
max_value = 0

for _ in range(n):
    x, y = map(int, input().split())
    t.append(x)
    p.append(y)

for i in range(n-1, -1, -1):
    time = t[i] + i
    if time <= n:
        dp[i] = max(p[i] + dp[time], max_value)
        max_value = dp[i]
    else:
        dp[i] = max_value

print(max_value)

- 해설📖

https://velog.io/@ji-vvon/06-3.-%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4#--%ED%95%B4%EC%84%A4-2

---

📝문제2. 백준 18353번(병사 배치하기)

- 문제

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

- 코드💻

n = int(input())
array = list(map(int, input().split()))
array.reverse()

dp = [1] * n
for i in range(1, n):
    for j in range(0, i):
        if array[j] < array[i]:
            dp[i] = max(dp[i], dp[j] + 1)

print(n-max(dp))

- 해설📖

https://velog.io/@ji-vvon/06-4.-%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4#--%ED%95%B4%EC%84%A4-1

---

📝문제3. 금광

- 문제

- 코드💻

def maxGold(arr, x, y):
    
    for j in range(1, y):
        for i in range(x):
            if i == 0:
                left_top = 0
            else:
                left_top = arr[i-1][j-1]
            if i == x-1:
                left_btm = 0
            else:
                left_btm = arr[i+1][j-1]
            left = arr[i][j-1]
            arr[i][j] = max(left_top, left, left_btm)+arr[i][j]
 
    finals=[]
    for i in range(x):
        finals.append(arr[i][y-1])
    return max(finals)
 
t = int(input())
 
for _ in range(t):
    n,m = map(int, input().split())
    arr=[]
    temp = list(map(int, input().split()))
    for i in range(0, len(temp), m):
        arr.append(list(temp[i:i+m]))
    print(maxGold(arr,n,m))

---

📝문제4. 편집 거리 문제