이 문제는 풀이법이 잘 떠오르지 않았다.
문자열 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 로 처리해줘야한다는 걸 알았다.
내가 완전히 이해한 건지는 모르겠지만 다음에 내 힘으로 다시 풀어보자.
이 문제는 물건을 무게 기준 내림차순으로 정렬한 후, 앞에서부터 각 물건을 담을 때의 최대값을 저장해가려고 한다.
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()
이 문제를 다시 접해도 풀 수 있을까 하는 의문이 든다.
내 힘으로 풀 수 있을 때까지 반복해보자!