06-3. 다이나믹 프로그래밍 문제풀이

📝문제1. 금광

- 문제

- 코드💻

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))

- 해설📖

1. 왼쪽 위에서 오는 경우
2. 왼쪽 아래에서 오는 경우
3. 왼쪽에서 오는 경우

이 경우 중 가장 많은 금을 가지고 있는 경우를 테이블에 저장해주어 문제를 해결할 수 있다.

참고 블로그
https://velog.io/@keroro3030/%EC%9D%B4%EA%B2%83%EC%9D%B4-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8%EB%8B%A4-Q31.%EA%B8%88%EA%B4%91-%ED%8C%8C%EC%9D%B4%EC%8D%ACDP

---

📝문제2. 백준 1932번(정수 삼각형)

- 문제

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

- 코드💻

from sys import stdin
n = int(stdin.readline())
dp = []
for _ in range(n):
    dp.append(list(map(int, stdin.readline().split())))

for i in range(1, n):
    for j in range(i+1):
        # 왼쪽 위에서 내려오는 경우
        if j == 0:
            up_left = 0
        else:
            up_left = dp[i-1][j-1]
        # 바로 위에서 내려오는 경우
        if j == i:
            up = 0
        else:
            up = dp[i-1][j]
        # 최대 합을 저장
        dp[i][j] = dp[i][j] + max(up_left, up)

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

- 해설📖

책에 있는 코드인데 개인적으로는
https://jiwon-coding.tistory.com/120
이 블로그에 있는 코드가 좀 더 이해하기 쉬웠던 것 같다.

---

📝문제3. 백준 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)

- 해설📖

뒤쪽 날짜부터 거꾸로 계산하며 문제를 해결할 수 있다. 즉, 뒤쪽부터 매 상담에 대하여 '현재 상담 일자의 이윤(p[i]) + 현재 상담을 마친 일자부터의 최대 이윤(dp[t[i] + i])'을 계산하면 된다. 이후 계산된 각각의 값 중에서 최댓값을 출력하면 된다.

dp[i] = i번째 날부터 마지막 날까지 낼 수 있는 최대 이익
이라고 하면 점화식은 dp[i] = max(p[i] + dp[t[i] + i], max_value)가 된다. 이때 max_value는 뒤에서부터 계산할 때 현재까지의 최대 상담 ㄱ므액에 해당하는 변수이다.

---

모든 내용은 '이것이 코딩 테스트다 with 파이썬(나동빈)' 책과 유튜브 강의를 기반으로 작성한 글입니다.