반복문에서 경우의 수를 나누는 방법

1. 문제

 

여러개의 음료수가 준비되어 있는데 각 음료수가 a개있고 1개당 b리터만큼 존재하고 1개당 c 칼로리의 열량을 가진다.

 

주어진 음료수에 대한 정보가 담겨있는 배열의 각 원소가 [a,b,c] 형태로 주어지고

 

p리터만큼 음료수를 마시고자 한다.

 

최대로 열량을 섭취하고자 할 때 최대 열량을 return하도록 함수를 완성한다면?

 

단, p리터 이전에 한번 마시기 시작한 음료수는 끝까지 다 마셔야한다고 가정한다.

 

그리고 한번에 a개의 음료수를 모두 마실 필요 없이 a개중 일부만 마시고 다른 음료수를 마신 다음에 못마신 음료수를 다시 마셔도 된다.

 

예를 들어 [[3,1,1],[1,2,2]]의 음료수 정보가 주어지고 p=3리터만큼 마시고자 할 때 총 4칼로리의 최대 열량을 얻을 수 있다.

 

첫번째 3개 있는 음료수 중 2개를 먼저 마시면 2리터를 마신건데 2번째 음료수를 마시면 총 4리터를 마신거지만 3리터 이전에 마셔서 남기지 않고 전부 다 마신다고 가정한다.

 

 

2. 되돌아보기

 

탐욕법으로 어떻게 하면 최대 열량을 섭취할 수 있을지 최적을 생각한거 좋았는데 어떻게 하면 최적일지가 쉽지는 않다

 

일반적으로 최적을 단순하게만 생각하면 열량이 최대이고 리터는 최소인 음료수를 먼저 마시는게 좋을테니까 열량이 큰 순서대로, 리터가 최소인대로 정렬하자

 

근데 이렇게 생각하면 [[3,1,1],[1,2,2]] , p=3인 경우 [1,2,2]를 먼저 마셔서 2칼로리 섭취하고 [3,1,1]중 하나를 먼저 섭취할 수 밖에 없고 최대 4칼로리인데도 3칼로리밖에 섭취를 하지 못한다. 

 

그렇다면 어떻게 해야할까?

 

최대 열량을 마셔야하는데 마셔야하는 리터 수가 제한되어 있으므로 

 

리터당 열량이 큰 음료수일수록 먼저 마시는게 유리하다

 

그래서 음료수 배열에서 하나씩 뽑아낸 다음 2번째 원소인 열량과 1번째 원소인 리터를 가지고 열량/리터 정보를 추가해서 열량/리터가 큰 순서대로, 리터가 작은 순서대로 정렬해야한다.

 

new_beverage = []

for a,b,c in beverages:
    
    new_beverage.append([a,b,c,c/b])
    

sorted_beverage = sorted(new_beverage, key = lambda item: [-item[3],item[1]])

 

몇가지 고려해야할 중요한 부분이 있었는데

 

음료수 종류를 한번에 모두 다 마실 필요는 없다는 점

 

예를 들어 [[3,1,1],[1,2,2],[4,1,2]]로 주어지면 첫번째 음료수를 2개 마시고 세번째 음료수를 3개 마시고 두번쨰 음료수를 1개 마신 뒤 첫번째 음료수 나머지 1개를 마셔도 된다는 점

 

그런데 단순히 위와 같이 정렬해서 for문을 돌아서 최대 열량을 구하면 음료수 마시는 것을 중간에 stop하기가 쉽지 않다

 

그래서 개수 자체는 큰 의미가 없어서 for문에서 음료수 정보 a,b,c를 뽑아내는데 new_beverage에 [b,c,c/b]를 a개만큼 똑같이 집어넣으면 음료수를 1개씩만 마실 수 있다

 

new_beverage = []

for a,b,c in beverages:

    for _ in range(a):
    
        new_beverage.append([b,c,c/b])
        
sorted_beverage = sorted(new_beverage, key = lambda item: [-item[2],item[0]])

 

이렇게 하면 음료수가 1개씩 들어가면서

 

리터당 열량이 큰 순서대로 음료수가 정렬이 되고 리터당 열량이 같은 경우는 리터가 최소인 경우가 앞에 오도록 정렬이 된다.

 

 

이렇게 하는 경우 마지막으로 문제가 되는 부분이 p리터 이전에 한번 마시기 시작한 음료수는 끝까지 다 마셔야한다고 가정한다는 부분

 

 

[[3,1,1],[1,2,2]] , p=3인 경우 [[1,1,1.0],[1,1,1.0],[1,1,1.0],[2,2,1.0]] 으로 바뀔텐데

 

단순히 for문을 돌면서 하나씩 빼자니 [1,1,1.0],[1,1,1.0] 이 2개는 마실 수 있는데

 

최대가 될려면 [2,2,1.0] 얘를 마셔야하는데 for문이 순서대로 빠지니까 [1,1,1.0] 얘를 마시게 되는 경우가 문제다

 

그렇다고 정렬을 다시해야하느냐??

 

for문을 돌면서 마시는 리터만큼 p에서 빠져나갈텐데 반복문을 돌다가 어느 순간부터는 p가 0이하가 될 것이다.

 

p가 0이하가 되는 순간부터는 바로 직전까지는 마셔도 최대 열량의 순간이라는 뜻

 

p가 0이하인 순간부터는 new_beverage에 음료수가 남아 있다면 경우의 수를 나눠서 섭취한 열량이 여러가지가 생길 수 있어서 리스트에 넣고 나중에 최댓값을 구하는 전략을 취함

 

p가 0이하인 순간에 지금까지 마신 열량을 리스트에 저장해두고

 

현재 마신 음료수의 열량과 리터 정보는 남아 있으니까 역산을 해서 p를 복원한 다음에

 

다음 반복문을 돌도록 한다

 

kcal_list = []

total_kcal = 0

for l,kcal,_ in sorted_beverage:

    p -= l
    
    total_kcal += kcal
    
    if p <= 0:
        
        kcal_list.append(total_kcal)
        
        p += l
        
        total_kcal -= kcal
        
answer = min(kcal_list)

return answer

 

이렇게 역산을 해서 반복문을 도는 중에도 경우의 수를 나눌 수 있다는 점을 기억하자