11.21 알고리즘 문제풀이

코테 연습

 

다이나믹 프로그래밍

첫 번째

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

12865번: 평범한 배낭

import sys
input = lambda: sys.stdin.readline().rstrip()

N, K = map(int, input().split())
items = sorted([list(map(int, input().split())) for _ in range(N)], reverse=True)

dp = [[0]*(K+1) for _ in range(N)]
init_w, init_v = items[0]
for idx in range(init_w, K+1):
    dp[0][idx] = init_v

for r, item in enumerate(items[1:], start=1):
    w, v = item
    for c in range(w, K+1):
        dp[r][c] = max(dp[r-1][c-w]+v, dp[r-1][c])
print(dp[-1][K])

유명한 냅색 문제라고 한다.

어려웠다.

다만, 2차원 배열로만 풀 수 있는 건 아닌거 같아서 다시 풀어봐야겠다.

이전에 퇴사 문제과는 아이템을 한번만 사용해야한다는 점에서 유사하다고 생각했고

같은 이유로 동전문제와는 다르다고 생각했다.

 

items에서 내림차순으로 정렬한 이유는

dp table 순회 반복문에서 컬럼을 w로 시작해도 괜찮도록 하기 위함이다.

그렇지 않으면 위의 행(행에 해당하는 아이템을 넣기 전 상태)에서 값을 가져와야한다.

 

두 번째

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

9251번: LCS

import sys
input = lambda: sys.stdin.readline().rstrip()

A, B = input(), input()
dp = [[0]*len(B) for _ in range(len(A))]

for b_idx in range(len(B)):
    if B[b_idx] == A[0]:
        for idx in range(b_idx, len(B)):
            dp[0][idx] = 1
        break

for a_idx in range(len(A)):
    if B[0] == A[a_idx]:
        for idx in range(a_idx, len(A)):
            dp[idx][0] = 1
        break

for a_idx in range(1, len(A)):
    for b_idx in range(1, len(B)):
        if A[a_idx] == B[b_idx]:
            dp[a_idx][b_idx] = dp[a_idx-1][b_idx-1]+1
        else:
            dp[a_idx][b_idx] = max(dp[a_idx][b_idx-1], dp[a_idx-1][b_idx])
# print(*dp, sep="\n")
print(dp[-1][-1])

2차원 dp 문제로 이해하고 풀었다.

2차원 dp는 점화식의 시작값을 어떻게 넣는 것이 깔끔할지 고민된다.