글 읽기 - 반례가 궁금합니다...

dbsrlskfdk 2년 전 0

dp로 구현한 느낌은 아니지만, 테스트 케이스, 질문게시판 반례들을 다 대입해도 정답으로 나옵니다..

근데 막상 제출을 하면 3퍼센트에서 틀렸다고 나오네요..

어떤 반례가 존재할지 궁금합니다..

N, K = map(int, input().split(" "))
item_list = [list(map(int, input().split(" "))) for i in range(N)]
item_list.sort()

dp = [[0, 0] for i in range(N)] # [weight_sum, value_sum]

for i in range(N):
    if item_list[i][0] <= K:
        dp[i][0] = item_list[i][0]
        dp[i][1] = item_list[i][1]
        for j in range(N):
            if j != i:
                if dp[i][0] + item_list[j][0] <= K:
                    dp[i][0] += item_list[j][0]
                    dp[i][1] += item_list[j][1] 
    else:
        continue
                
result_dp = [dp[i][1] for i in range(N)]
print(max(result_dp))

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

문제

문제

출처

ICPC

반례가 궁금합니다...

dbsrlskfdk 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말