9251 LCS, 1495 기타리스트, 2655 가장높은탑쌓기

9251 LCS, 1495 기타리스트, 2655 가장높은탑쌓기

 

9251 LCS

x = input()
y = input()

dp = [[0] * (len(y) + 1) for _ in range(len(x) +1)

for i in ragne(1, len(x)+1):
	for j in range(1, len(y)+1):
		if x[i-1] == y[j-1]:
			dp[i][j] = dp[i-1][j-1] + 1
		else:
			dp[i][j] = max(dp[i][j-1], dp[i-1][j])
			
print(dp[len(x)][len(y)]) 

- 0으로 이루어진 행렬 만든 후 각 행과 열에 개별적인 수치를 이용하여 행렬을 채움

 

 

1495 기타리스트

# n개 곡 연주
# 매번 곡이 시작하기 전 볼륨 변경
# 다음 곡의 크기만큼 더하거나 빼기 가능, 0 <= P <= M
# 마지막 곡을 연주할 수 있는 볼륨 중 최댓값 구하기
n, s, m = map(int, input().split())
array = list(map(int, input().split()))

dp = [[0] * (m+1) for _ in range(n+1)]
dp[0][s] = 1

for i in range(1, n+1):
	for j in range(m+1):
		if dp[i-1][j] == 0:
			continue
		if j - array[i-1] >= 0:
			dp[i][j - array[i-1]] = 1
		if j + array[i-1] <= m:
			dp[i][j + array[i-1]] = 1
			
result = -1
for i in range(m, -1, -1):
	if dp[-1][i] == 1:
		result = i
		break

print(result)

- 모든 경우의 수를 전부 구해야되는줄 알았는데 이렇게 쉽게 가능하다니 역시 아이디어 싸움이다.

 

 

2655 가장높은탑쌓기

#    밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다.
#    밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다.
#    무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다.
#    넓이, 높이, 무게

n = int(input())
array = []

array.append((0, 0, 0, 0))
for i in range(1, n+1):
	area, height, weight = map(int, input().split())
	array.append((i, area, height, weight))
	
# 무게 기준 정렬
array.sort(key=lambda x:x[3])

dp = [0] * (n+1)

for i in range(1, n+1):
	for j in range(0, i):
		if array[i][1] > array[j][1]:
			dp[i] = max(dp[i], dp[j] + array[i][2])
			
max_value = max(dp)
index = n
result = []

while index != 0:
	if max_value == dp[index]:
		result.append(array[index][0])
		max_value -= array[index][2]
	index -= 1
	
result.reverse()
print(len(result))
[print(i) for i in result]

하나 정렬하고 다른걸로 비교하는건 알았는데 역으로 무게 돌리는 연산은 익숙해질 필요 있음