글 읽기 - 두 코드를 짜봤는데, 효율이 괜찮을 것 같은 코드가 시간초과가 나네요

freezing16 1년 전 0

Code 1으로 풀어서 제출했는데

굳이 2차원 안쓰고 1차원으로도 풀 수 있을 것 같아서

Code 2로 제출했더니 시간초과가 떴습니다.

Code 2가 오히려 시간이 적게 걸릴 줄 알았으나 아니었습니다.

초보라 메모리 관련해선 무지인데 혹시 메모리 때문인가요 ?

설명해주시면 정말 감사하겠습니다.

Code 1) 
N, K = map(int, input().split())

sum_value = [[0]*(K+1) for i in range(N+1)]
W = [0]*(N+1)
V = [0]*(N+1)

for i in range(1, N+1):
    W[i], V[i] = map(int, input().split())

    for j in range(1, K+1):
        if W[i] > j:
            sum_value[i][j] = sum_value[i-1][j]
        else:
            sum_value[i][j] = max(sum_value[i-1][j], V[i]+sum_value[i-1][j-W[i]])

print(sum_value[N][K])





Code 2) 
N, K = map(int, input().split())

sum_value = [0]*(K+1)
items = []

for _ in range(N):
    w, v = map(int, input().split())
    items.append((w, v))

    for item in items:
        w, v = item 

        for i in range(K, w-1, -1):
            sum_value[i] = max(sum_value[i], sum_value[i-w]+v)

print(sum_value[-1])

zenith82114 1년 전 1

33~37줄의 들여쓰기를 하나씩 빼줘야 할 것 같네요.

freezing16 1년 전 0

와우 정말 감사합니다 !

바보였네요 제가 ㅋㅋㅋ

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

문제

문제

출처

ICPC

두 코드를 짜봤는데, 효율이 괜찮을 것 같은 코드가 시간초과가 나네요

freezing16 1년 전 0

zenith82114 1년 전 1

freezing16 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말