[백준] 4781번 사탕 가게 ★

💡문제접근

• 배낭 문제 형태의 동적 프로그래밍 문제였다. 다만 다른 배낭 문제와의 차이점이 있었다.
  일반적인 배낭 문제의 경우 배낭에 들어갈 수 있는 각 물건의 개수를 최대 1개로 조건을 걸어두는데 이 문제는 각 사탕의 개수가 매우 많아 원하는 만큼의 사탕을 넣을 수 있다는 것이 조건이었다.
• 질문게시판에 있는 내용을 보니 2차원 배열로 풀게 되면 무조건 시간초과가 나와 1차원 배열로 풀어야 한다는 조언이 많았다.
• 입력에 넣는 값이 0 0.00인 경우 무한 반복문이 멈춰야하는데 처음엔 int(m * 100)으로 0을 맞춰주어 반복문의 조건을 걸어줬는데 이렇게 해줬더니 계속 메모리초과가 나오게 되었다. 구글링하여 이유를 살펴보니 0.5을 더해줘야 한다는 내용이 많았는데 0.5를 더하는 이유는 실수 오차가 발생하여 m * 100이 정확히 정수가 되지 않을 수 있고 특히 그 값이 조금 모자라서 0.999999와 같은 형태가 되는 경우 int() 자료형을 취해주면 1이 아니라 0이 되는 문제가 발생하기 때문이라고 나와있었다. 다른 사람들을 보니 아직 배워야 할 점이 많은 것 같다는 것을 절실히 느꼈던 문제였다.

💡코드(메모리 : 115404KB, 시간 : 1528ms, PyPy3로 제출)

import sys
input = sys.stdin.readline

while True:
    n, m = map(float, input().strip().split())
    n, m = int(n), int(m * 100 + 0.5)
    if n == 0 and m == 0:
        break

    # dp 테이블 : 주어진 돈을 사용해서 구매할 수 있는 가장 높은 칼로리
    dp = [0] * (m+1)
    for _ in range(n):
        c, p = map(float, input().strip().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(max(dp))

📌 Python3으로 제출한 결과 시간초과(TLE)가 발생함

💡소요시간 : 37m