글 읽기 - 메모리초과문제

bluevulpe270 1년 전 0

아무리 생각해도 최대 시간복잡도는 O[N"2]인데

시간초과는 안나는대신 메모리 초과되는 부분은 어떻게 해결해야 할지 감이 안잡히네요 ㅠㅠ

고수님들의 조언 부탁드립니다.

N, K = map(int, input().split())
P = [(0,0,0)]
for i in range(N):
    itm_wght, itm_prfts, itm_cnts = map(int, input().split())
    itm_val = itm_prfts / itm_wght
    itm_val = round(itm_val, 2)
    for _ in range(itm_cnts):
        P.append((itm_wght, itm_prfts, itm_val))

P.sort(key = lambda x : (-x[2], x[1]))
W = [0]
V = [0]
for data in P:
    W.append(data[0])
    V.append(data[1])
itm_count = len(P)
knapsack = [[0] * (K+1) for _ in range(itm_count+ 1)]

for itm_num in range(1, itm_count+1):
    for bag_size in range(1, K+1):
        if bag_size < W[itm_num]:
            knapsack[itm_num][bag_size] = knapsack[itm_num-1][bag_size]
        elif bag_size > W[itm_num]:
            knapsack[itm_num][bag_size] = max(knapsack[itm_num-1][bag_size-W[itm_num]]+V[itm_num], knapsack[itm_num-1][bag_size])
        elif bag_size == W[itm_num]:
            knapsack[itm_num][bag_size] = max(V[itm_num],knapsack[itm_num-1][bag_size])

print(knapsack[itm_count][K])

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

메모리초과문제

bluevulpe270 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말