2021년 1학기 알고리즘응용 10주차

10주차 과제 - 칼로리 계산(다이나믹 프로그래밍)

사용 언어 : python
해결 날짜 : 2021-05-10

느낀점 및 해결 과정 :

문제에서 소수점 둘째 자리까지 생각한다고 했으므로 인덱싱하기 위해 식비를 나타내는 budget에 100을 곱해주면서 문제를 해결하였다.
최적화를 진행하면서, 0으로 초기화 해주는 작업, 넣고자 하는 음식의 가격이 넣을 수 있는 가격보다 크다면 이차원 리스트에서 바로 위의 값을 넣는 작업을 한다.
그 후 넣고자 하는 음식의 칼로리 + 넣을 수 있는 최대 칼로리 / 넣고자 하는 음식의 칼로리 + 넣고자 하는 음식의 가격을 뺀 가격의 최대 칼로리(수량은 무제한이므로) / 바로 위의 값 의 세 값 중에서 칼로리가 가장 큰 값을 골라 최적화한다.
최적화를 모두 마치면 가장 마지막 인덱스에 주어진 예산으로 구매할 수 있는 식품의 최대 칼로리를 구할 수 있다.
시간 복잡도 :
- len() : O(1)
- 최적화 2중 for문 : O(N+1) * O(B100+1) (N = 음식의 개수, B100 = 식비*100(소수 둘째자리))
- max() : O(3) / len() : O(1)
- 따라서 O(1 + (N+1)(100B+1)3*1) = O(NB) 의 시간 복잡도를 갖는다.
코드

import numpy

def calculate_calorie(food, calorie, price, budget):
    n = len(food)
    # 소수점 둘째 자리 까지 인덱싱하기 위해 100 곱하여 2차원 리스트 0으로 초기화
    opt = [[0 for x in range(int(budget*100) + 1)] for y in range(n+1)]
    for i in range(n+1):
        for p in range(int(budget*100) + 1):
            if i == 0 or 0 <= p < 100: # 0 <= p < 100이면 원래 값은 0.xx 였으므로 값은 0
                opt[i][p] = 0
            elif int(price[i-1]*100) > p: # 넣고자 하는 음식의 가격이 넣을 수 있는 가격보다 크다면 위의 값 넣기
                opt[i][p] = opt[i-1][p]
            else:
                # 넣고자 하는 음식의 칼로리 + 넣을 수 있는 최대 칼로리
                # 넣고자 하는 음식의 칼로리 + 넣고자 하는 음식의 가격을 뺀 가격의 최대 칼로리 (음식을 무한으로 담을 수 있기 때문)
                # 바로 위의 값의 세 값 중에서 칼로리가 가장 큰 값을 골라 최적화
                opt[i][p] = max(calorie[i - 1] + opt[i - 1][p - int(price[i - 1] * 100)],
                                calorie[i - 1] + opt[i][p - int(price[i - 1] * 100)],
                                opt[i-1][p])
    return opt[len(opt)-1][len(opt[0])-1]

# N = 음식의 개수, K = 예산
N, K = input().split()
N = int(N)
K = float(K)

# price = 각 식품의 가격, calorie = 칼로리
food = []
price = []
calorie = []
# 각 식품와 가격과 칼로리 입력
for i in range(N):
    A, B = input().split()
    A = float(A)
    B = int(B)
    food.append(i)
    price.append(A)
    calorie.append(B)

print(calculate_calorie(food, calorie, price, K))