#Dynamic_programming #예시문제

변수 세 개를 받아서, 최대 수익을 구하는 함수 만들기

그 세 개의 변수란, 1) 판매 개수에 따른 매출에 대한 리스트. 즉, 리스트의 인덱스가 판매 개수이며 리스트의 실제값은 인덱스값만큼 판매하였을 때의 매출액에 해당한다. 2) 판매하고자 하는 제품의 개수 3) 특정 개수 별 최대 매출액이 저장되어 있는 딕셔너리

이 문제 또한 앞서 소개한 두 개의 전략처럼, Memoization과  Tabulation 각각의 전략으로 접근 가능하다. 

먼저 #Memoization인 경우 다음과 같이 풀 수가 있다. 

def max_profit_cache(p_of_list, n, cache):
	#만약, 판매n의 개수가 0이거나 1인 경우에는 price_list에 있는 것을  
    #그대로 리턴하면 된다. 단, 이 값또한  cache에 저장하는 것을 잊지말자*(내가 놓친 부분)
    
    if n < 2:
    	cache[n] = p_of_list[n]
    
    if n in cache:
    	return cache[n] #계산한 값이 cache에 있을 경우 그대로 리턴하면 된다. 
    
    else:
    	cache[n] = max_profit_cache(p_of_list, n-1, cache) + max_profit_cache(p_of_list, 1, cache)
        
    	for i range (1, n//2+1): 가능한 모든 경우의 수를 생각해야 하므로,
        	temp = max_profit_cache(p_of_list, i, cache) + max_profit_cache(p_of_list, n-i, cache)
            
            if temp > cache[n]:
            	cache[n] = temp
     	if n < len(p_of_list):
        	cache[n] < p_of_list[n]:
            	cache[n] = p_of_list[n]
    
    return cache[n]
    
#실제 최대 매출액을 구하는 함수, 들어가는 인자는 price_list와 n
def max_profit(p_of_list, n):
	max_cache = {} #저장하는 딕셔너리 생성
    
    return max_profit_cache(p_of_list, n, cache)
            
        
        

 

다른 풀이와 비교해봤을 때, 파이썬의 max 함수를 사용한 경우도 있었다.

max()는 여러 값들의 나열중에서 최대값을 리턴해주는 함수이다. (리스트나 값 자체들을 나열한 것도 받는다)

p_of_list에 포함되는 값인 경우 range(1, n//2+1)의 조합값들과 비교하여 max값으로 최종값으로 산출하였다.