글 읽기 - 반례 부탁 드립니다 ㅜㅜ

gunwook0307 2년 전 0

뭔가 맞게 접근한것 같은데 계속 틀리네요...

혹시 반례가 있을까요? ㅜㅜㅜ

# DP로 해결하는 것이 좋다고 한다.
# 배낭 문제와 매우 비슷하다.
def solution_DP(list_coffee, n, k):
    if k == 0:
        return 0
    full_cafe = sum(list_coffee)
    list_coffee = sorted(list_coffee)
    dp = []
    dp.append([0] * (full_cafe + 1))

    for i in range(1, n + 1):
        dp.append([0] * (full_cafe + 1))
        for c in range(1, full_cafe + 1):

            if c == list_coffee[i - 1]:
                dp[i][c] = 1
                continue

            val = dp[i - 1][c - list_coffee[i - 1]]

            if list_coffee[i - 1] < c and val != 0:
                dp[i][c] = val + 1
                continue

            else:
                dp[i][c] = dp[i - 1][c]
                continue

        for i in dp:
            print(i)
        print()

    if full_cafe < k or dp[-1][k] == 0:
        return -1
    else:
        return dp[-1][k]


print(solution_DP(list_coffee, n, k))

adfsfsf 2년 전 0

입력을 받는 부분이 없네요? 잘못 올리신 건가요?

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

문제

문제

출처

ICPC

반례 부탁 드립니다 ㅜㅜ

gunwook0307 2년 전 0

adfsfsf 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말