[파이썬] 백준 4781 : 사탕가게 (골드4)

[파이썬] 백준 4781 : 사탕가게 (골드4)

4781번: 사탕 가게

---

문제

---

풀이

0. 방향성 생각

• 냅색인데, 같은 가게에서 사탕을 무제한으로 살 수 있다(가격이 되는 한).

1. 입력

import sys
input = lambda: sys.stdin.readline().rstrip()

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

    info = []
    for _ in range(n):
        a,b = input().split()
        info.append((int(a),int(float(b)*100+0.5)))

•  

2. 함수 정의

    dp = [0]*(m+1)

    kcal,cost = info[0]
    for spend in range(cost,m+1,cost):
        dp[spend] = kcal*(spend//cost)

    for stage in range(n-1):
        kcal,cost = info[stage+1]
        temp = [0]*(m+1)
        for spend in range(m+1):
            temp[spend] = dp[spend]
            if spend >= cost:
                temp[spend] = max(temp[spend],temp[spend-cost]+kcal)
        dp = temp
    print(max(dp))

• 메모리 터져서 전체 DP 테이블을 정의하지 않고 현재 상태랑 직전 상태만 기억한다.
• 현재 DP 테이블을 먼저 현재 가게에서 살 수 있는 사탕으로 채워준다. (x달러에 y칼로리, 2x달러에 2y칼로리 ...)
• 특정 node를 채울때는, 현재 저장한 값과 이전 node에서 사탕을 산 최대값

 

---

전체코드

import sys
input = lambda: sys.stdin.readline().rstrip()

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

    info = []
    for _ in range(n):
        a,b = input().split()
        info.append((int(a),int(float(b)*100+0.5)))

    dp = [0]*(m+1)

    kcal,cost = info[0]
    for spend in range(cost,m+1,cost):
        dp[spend] = kcal*(spend//cost)

    for stage in range(n-1):
        kcal,cost = info[stage+1]
        temp = [0]*(m+1)
        for spend in range(m+1):
            temp[spend] = dp[spend]
            if spend >= cost:
                temp[spend] = max(temp[spend],temp[spend-cost]+kcal)
        dp = temp
    print(max(dp))

 

코멘트

골4치고 조금 까다롭지 않았나... 시간이나 메모리나

메모리는 512인데 왜터지는지