[BOJ] 4781 - 사탕 가게 (Python)

 

 

아이디어

 

2293번 동전 1 문제와 유사한 문제로, 동적 계획법으로 가진 돈으로 구매할 수 있는 가장 높은 칼로리를 구한다.

 

 

풀이

 

동적 계획법을 적용하기 위해 돈의 단위를 정수형으로 바꾼다.

0.5를 더하는 이유는 실수 계산 시 부동소수점 오차로 인해 정수 값이 올바르게 나오지 않을 수 있기 때문이다.

 

사탕 정보를 정렬하여 같은 칼로리에 대해 가장 낮은 가격의 사탕만을 저장한다.

 

import sys

input = sys.stdin.readline

def solution():
    while 1:
        n, m = input().split()
        n, m = int(n), int(float(m)*100+0.5)
        if n == m == 0:
            break
        temp = []
        for _ in range(n):
            c, p = input().split()
            c, p = int(c), int(float(p)*100+0.5)
            temp.append((c, p))
        temp.sort()
        candies = [temp[0]]
        for i in range(1, n):
            if temp[i][0] > candies[-1][0]:
                candies.append(temp[i])
        dp = [0]*(m+1)
        for c, p in candies:
            for i in range(p, m+1):
                cnt = dp[i-p]+c
                if cnt > dp[i]:
                    dp[i] = cnt
        print(dp[-1])

solution()

 

 

실수 계산 대신 문자열로 처리하여 정수 값을 구할 수 있다.

n, m = input().split()
n, m = int(n), int(''.join(m.split('.')))

 

사탕 정보를 전처리하지 않고 바로 동적 계획법을 사용하면 시간 초과가 발생한다.

# 시간 초과 코드
dp = [0]*(m+1)
for _ in range(n):
    c, p = input().split()
    c, p = int(c), int(float(p)*100)
    for i in range(p, m+1):
        cnt = dp[i-p]+c
        if cnt > dp[i]:
            dp[i] = cnt
print(dp[-1])