글 읽기 - 시간초과가 나는데..해결 방법 질문 드립니다

dldjsth 2년 전 0

이 코드로는 시간이 너무 많이 걸리나요? 여기서 dp를 어떻게 써야할지 감이 오질않습니다ㅜㅜ 방향성만 제시해주신다면 열심히 수정해보겠습니다

import sys
N, M=map(int, sys.stdin.readline().rstrip().split())
dy=[0]*(M+1)
for i in range(N):
    a=[]
    w, v=map(int, input().split())
    for j in range(w,M+1):
        t=True
        for k in a:
            if j-w == k[0]:
                if max(dy[j],k[1]+v)==k[1]+v:
                    a.append([j,dy[j]])
                dy[j]=max(dy[j],k[1]+v)
                t=False
                break
        if t:
            if max(dy[j],dy[j-w]+v)==dy[j-w]+v:
                a.append([j,dy[j-w]])
            dy[j]=max(dy[j],dy[j-w]+v)

print(dy[-1])

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

문제

문제

출처

ICPC

시간초과가 나는데..해결 방법 질문 드립니다

dldjsth 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말