4781 - 사탕 가게
문제
상근이는 선영이와 걸어가다가 사탕 가게를 지나가게 되었다. 갑자기 상근이는 선영이에게 사탕이 얼마나 건강에 안 좋은지 설명하기 시작했다. 선영이는 매우 짜증이 났고, 상근이에게 누가 더 건강이 안 좋아질 수 있는지 내기를 하자고 했다. 상근이는 내기를 그 즉시 받아들였다.
두 사람은 같은 돈을 가지고 가게에 들어가서 사탕을 산다. 이때, 구매한 사탕의 칼로리가 더 큰 사람이 내기에서 이기게 된다.
상근이는 잠시 화장실에 갔다온다고 핑계를 댄 뒤에, 노트북을 열고 사탕 가게의 시스템을 해킹하기 시작했다. 이 시스템에는 현재 사탕 가게에 있는 사탕의 가격과 칼로리가 모두 등재되어 있다. 각 사탕의 개수는 매우 많기 때문에, 원하는 만큼 사탕을 구매할 수 있다. 또, 사탕은 쪼갤 수 없기 때문에, 일부만 구매할 수 없다.
사탕 가게에 있는 모든 사탕의 가격과 칼로리가 주어졌을 때, 어떻게 하면 칼로리의 합이 가장 크게 되는지를 구하는 프로그램을 작성하시오.
코드
import sys
input = sys.stdin.readline
while True:
n, m = map(float, input().split())
n, m = int(n), int(m * 100 + 0.5)
if n == 0 and m == 0:
break
dp = [0 for _ in range(m+1)]
for _ in range(n):
c, p = map(float, input().split())
c, p = int(c), int(p * 100 + 0.5)
for i in range(p, m+1):
dp[i] = max(dp[i], dp[i-p] + c)
print(dp[m])한마디
파이썬으로 AC를 못받은 코드이긴 하다. 다른 사람들 코드를 봤을 때 동일한 로직으로 푼 씨나 씨플플에서는 통과되던데, 왜 100%에서 계속 틀렸다고 뜨는지 모르겠다.
