글 읽기 - 과연 이 코드가 다이나믹 프로그래밍이라고 할 수 있나요??

qawesdxc 3년 전 0

정답처리된 코드입니다.

이렇게 푼것을 다이나믹 프로그래밍이라고 할 수 있을까요??

N, K = list(map(int, input().split()))
Knap = []
candidate = {}

def set_Knap():
    global Knap
    
    import sys

    for _ in range(N):
        w, v = list(map(int, sys.stdin.readline().split()))
        Knap.append((w, v))

def set_candidate():
    candidate[K] = 0

def init():
    set_Knap()
    set_candidate()
    return

def sort_candidate():
    global candidate
    
    cand = list(candidate.items())

    candidate = dict(sorted(cand, key = lambda x : x[0], reverse = True))

def record_candidate():
    global candidate
    
    for (w, v) in Knap:
        cand = list(candidate.items())
        for remain, values in cand:
            if(remain < w):
                break
            
            if(remain >= w):
                if(remain - w in candidate.keys()):
                    candidate[remain - w] = max(candidate[remain - w], values + v)

                else:
                    candidate[remain - w] = values + v

        sort_candidate()

def print_result():
    values = candidate.values()
    print(max(values))

def main():
    record_candidate()
    print_result()
    return
    
if(__name__ == "__main__"):
    init()
    main()

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

문제

문제

출처

ICPC

과연 이 코드가 다이나믹 프로그래밍이라고 할 수 있나요??

qawesdxc 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말