[python] 동적 프로그래밍(Dynamic Programing)_백준 문제 풀이(9251번, 12865번)

이희진·2023년 3월 13일
0

9251번 문제 - LCS(Longest Common Subsequence)

이 문제는 풀이법이 잘 떠오르지 않았다.
문자열 a,b를 가지고 점화식을 그려보자면,

a[i] == b[j] 일 때,
LCS(a[i], b[j]) = LCS(a[i-1], b[j-1]) + 1

a[i] != b[j] 일 때,
LCS(a[i], b[j]) = LCS(a[i-1], b[j]), LCS(a[i], y[i-1])

import sys
a = list(sys.stdin.readline().strip())
b = list(sys.stdin.readline().strip())

dp = [[0]*len(b) for _ in range(len(a))]
for i in range(1, len(a)):
    for j in range(1, len(b)):
        if a[i] == b[j]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

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

!! 위의 코드는 자꾸 틀렸다..

a = input().strip()
b = input().strip()
 
dp = [[0 for j in range(len(b)+1)] for i in range(len(a)+1)]
 
for i in range(len(a)):
    for j in range(len(b)):
        if a[i]==b[j]:
            dp[i+1][j+1]=dp[i][j] + 1
        else:
             dp[i+1][j+1]=  max(dp[i+1][j], dp[i][j+1])
 
print(dp[-1][-1])

입력값의 길이 조건이 없는 게 찝찝했는데
다른 사람 풀이를 보고 나니 앞에 패딩을 넣고 인덱스를 +1 로 처리해줘야한다는 걸 알았다.
내가 완전히 이해한 건지는 모르겠지만 다음에 내 힘으로 다시 풀어보자.

12865번 문제 - 평범한 배낭

이 문제는 물건을 무게 기준 내림차순으로 정렬한 후, 앞에서부터 각 물건을 담을 때의 최대값을 저장해가려고 한다.

import sys
def solve():
    n, k = [int(x) for x in sys.stdin.readline().split()]
    table = [0] * (k+1)
    for _ in range(n):
        w, v = [int(x) for x in sys.stdin.readline().split()]
        if w > k:
            continue
        for j in range(k, 0, -1):
            if j + w <= k and table[j] != 0:
                table[j+w] = max(table[j+w], table[j] + v)
            table[w] = max(table[w], v)
        print(max(table))

solve()

결과는 실패..! 다시 풀어보잣

풀이 (다시 시도)

배낭에 담을 수 있는 무게의 최대값을 식으로 표현하자면

dp[i][j] = max(현재 물건 가치 + dp[이전 물건][현재 가방 무게 - 현재 물건 무게], dp[이전 물건]

이렇게 된다. dp를 왜 이중으로 해야하는지 이해가 안되었었는데, 각 무게에서 각각의 물체가 들어있을 경우 최대값을 기록해야하기 위해 이중 for문으로 채워준다.

[참고] 어떤 친절한 분이 이렇게 그림으로 설명해주신 걸 보고 겨우 이해했다.

import sys

def solve():
    n, k = [int(x) for x in sys.stdin.readline().split()]
    dp = [[0]*(k+1) for _ in range(n+1)]
    things = [(0,0)]
    for i in range(n):
        w, v = [int(x) for x in sys.stdin.readline().split()]
        things.append((w,v))
    for i in range(1, n+1):
        for j in range(1, k+1):
            w = things[i][0]
            v = things[i][1]
            if w > j:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], v + dp[i-1][j-w])
        
    print(dp[n][k])
    
solve()

이 문제를 다시 접해도 풀 수 있을까 하는 의문이 든다.
내 힘으로 풀 수 있을 때까지 반복해보자!

0개의 댓글