[ BOJ 4781 ] 사탕 가게(Python)

문제

https://www.acmicpc.net/problem/4781

냅색 기초 문제라고 해서 후딱 풀었다.
냅색 알고리즘을 모르신다면,, 함 읽어보세요~! (🔗 링크)

문제 풀이

구매할 수 있는 금액이 정해져있을 때, 최대의 칼로리를 구하는 문제다.

이전에 푼 냅색 문제와 동일하지만 입력이 조금 더럽다.

각 테스트 케이스의 첫째 줄에는 가게에 있는 사탕 종류의 수 n과 상근이가 가지고 있는 돈의 양 m이 주어진다. (1 ≤ n ≤ 5,000, 0.01 ≤ m ≤ 100.00) m은 항상 소수점 둘째자리까지 주어진다.

다음 n개 줄에는 각 사탕의 칼로리 c와 가격 p가 주어진다. (1 ≤ c ≤ 5,000, 0.01 ≤ p ≤ 100.00) c는 항상 정수, p는 항상 소수점 둘째자리이다.

입력의 마지막 줄에는 '0 0.00'이 주어진다.

사탕 종류의 수는 int형, 구매할 수 있는 금액은 float 형태다.
금액은 항상 소수점 둘째자리까지 주어진다고 해서 침착하게 곱하기 100을 해주었다.

그렇게 풀고 제출했는데 100% 까지 채점이 되다가 '틀렸습니다'가 떴다. (ㄱ-)..

질문 게시판을 찾아보니 (float 형태 * 100)을 해주면 부동소수점 오류가 발생한다고 한다.
👉🏻 https://www.acmicpc.net/board/view/51026

아래의 글에 적힌대로 (금액 * 100) + 0.5 를 해주니 결과가 잘나왔다.
👉🏻 https://www.acmicpc.net/board/view/63498

코드

import sys
input = sys.stdin.readline

while True:
    n, money = map(float,input().rstrip().rsplit())
    n = int(n)

    if n==0 and money==0.00:
        break

    money = int(money * 100)

    candies = []
    for _ in range(n):
        c, p = map(float,input().rstrip().rsplit())
        candies.append([int(c),int(p * 100 + 0.5)])

    #dp[i] = 돈이 i일때, 사탕 중 가장 높은 칼로리
    dp = [0] * 10001

    # candies[0]: 칼로리, candies[1]: 가격
    for i in range(1,money+1):
        for j in range(n):
            curr_candy_c = candies[j][0]
            curr_candy_m = candies[j][1]

            if (i < curr_candy_m):
                continue

            dp[i] = max(dp[i], dp[i-curr_candy_m] + curr_candy_c)

    print(dp[money])