백준 풀이

11049 행렬 곱셈 순서

정말 어렵게 다가왔다.

DP문제이다 보니 dp테이블을 만들어서 써먹으면 되겠다! 라는 틀 안에서 벗어날 수가 없었다.

풀이는 해당 블로그에서 참조했다.

# https://velog.io/@e_juhee/python-백준-11049-행렬-곱셈-순서-DP

import sys
input = sys.stdin.readline

# input
N = int(input())
Matrix = []
for _ in range(N):
    r, c = map(int, input().split())
    Matrix.append((r, c))

# dp[시작행렬][끝행렬] = 최소 연산 횟수
dp = [[0] * N for _ in range(N)]


def solve():
    global Matrix, dp

    for term in range(1, N):
        for start in range(N):
            if start + term >= N:
                break

            # term: 간격
            dp[start][start + term] = int(1e9)

            # pivot을 기준으로 왼쪽, 오른쪽을 묶어준다.
            for pivot in range(start, start + term):
                dp[start][start + term] = min(dp[start][start + term],
                                              dp[start][pivot] +
                                              dp[pivot + 1][start + term] +
                                              Matrix[start][0] * Matrix[pivot][1] * Matrix[start + term][1]
                                              )


# main
solve()
print(dp[0][N-1])

마지막 Matrix[start][0] * Matrix[pivot][1] * Matrix[start + term][1] 부분이 이해가 어려웠는데 설명하자면

(A, B, C), (D, E) 이렇게 묶어서 연산을 수행한다고 하면 Matrix[start][0]은 A의 행, Matrix[pivot][1]은 C의 열, Matrix[start + term][1]은 E의 열 이된다.
즉 마지막 두 묶음의 행렬곱을 합칠때 필요한 연산임을 나타낸다.

---

12865 평범한 배낭

전형적인 배낭(Knapsack) 문제이다.

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
# [weight, value]
bag = [[*map(int, input().split())] for _ in range(N)]

# dp[무게] = 해당 무게에서 얻을 수 있는 최고 가치
dp = [0] * 100_001

for weight, value in bag:
    for total_weight in range(100_000, weight - 1, -1):
        dp[total_weight] = max(dp[total_weight], dp[total_weight - weight] + value)

print(dp[K])

이 문제를 풀다가 두번째 for문에서 왜 역순으로 진행해야하는지 고민했었다.

결론적으로 말하자면, 오름차순으로 정렬하면 내가 현재 확인중인 item을 사용하는 경우로 갱신이 될 것이고, 그 이후엔 갱신된 값을 기반으로 연산을 수행하기 때문에 하나의 아이템을 재사용하게 된다.

이를 방지하기 위해서 역순으로 돌면서 값을 갱신한다. 갱신할 때 조건은 그 보다 가벼운(왼쪽에, 이전에) 상황에서의 최대값을 이용하기 때문에.

이를 3주차 초반에 풀이했던 동전문제와 연관지을 수 있다.

---

2624 동전 바꿔주기

import functools
import sys

input = sys.stdin.readline
INF = 10_000

# input
t = int(input())
k = int(input())
coins = []
for _ in range(k):
    price, num = map(int, input().split())
    coins.append((price, num))

dp = [0] * (t + 1)  # dp[price]: price 원을 만드는 동전의 조합
dp[0] = 1

# main
#
for p, n in coins:
    for money in range(t, 0, -1):
        for i in range(1, n + 1):  # 가용가능한 동전의 개수
            if money - p * i >= 0:
                dp[money] += dp[money - p * i]
print(dp[t])

여기서도 보면 money에 대한 for문은 거꾸로 돌아간다. 왜냐하면 dp[money]의 값이 현재 선택한 동전으로 가용한 조합이 가능한지 판단하는 중이기 때문에 현재 사용했다고 판단하는 값을 기반으로 또 한번 사용하는(재사용하는) 경우가 발생한다.