구름톤 챌린지 Week 3 - Day 15

https://level.goorm.io/exam/195697/과일-구매/quiz/1

구름톤 챌린지 3주, 15일차 문제 과일 구매이다.

문제를 어느정도 접해본 사람이라면, 위 문제를 보고 한 가지가 떠올라야 한다. '분할 가능한 배낭 문제'

가방 최대 한도가 소지한 돈(K)에 해당하고, 각 물건의 무게들은 포만감(C)에 해당한다.

 

fruits, MONEY = map(int, input().split())

fruit_list = []
for _ in range(fruits):
    fruit_price, fruit_full = list(map(int, input().split()))
    piece_full = fruit_full // fruit_price
    fruit_list.append([piece_full, fruit_price, fruit_full])

fruit_list.sort(key=lambda x: -x[0])

answer = 0
for piece_full,fruit_price, fruit_full in fruit_list:
    if MONEY >= fruit_price:
        answer += fruit_full
        MONEY -= fruit_price
        
    else:
        answer += MONEY * piece_full
        break
    
print(answer)

위에서 언급했던 것처럼 가방 한도가 가격으로, 물건 무게가 포만감으로 바뀌었을 뿐 문제 자체는 같다.

잘 알려진 분할 가능한 가방 문제이니 만큼, 모르더라도 쉽게 풀 수 있다.

동적 계획법 카테고리였다면, '0-1 가방 문제(0-1 knapsack problem)'가 나왔어야 했다. 

 

fruit_list = []
for _ in range(fruits):
    fruit_price, fruit_full = list(map(int, input().split()))
    piece_full = fruit_full // fruit_price
    fruit_list.append([piece_full, fruit_price, fruit_full])

비교를 위한 조각당 포만감(piece_full)을 추가로 계산하여 list에 넣어준다.

이때 가격은 1로 고정이고, 조각당 포만감(piece_full)과 총 가격(fruit_price)을 알고 있다.

따라서 연산으로 총 포만감(fruit_full)을 구할 수 있어 추가하지 않아도 상관없다.

하지만, 굳이 따로 또 연산을 하는 것보다 이미 주어진 값을 활용하는 것이 효율적이라 같이 저장한다.

 

fruit_list.sort(key=lambda x: -x[0])

최대의 포만감을 찾기 위한, 이 문제는 그리디 알고리즘이다.

가장 높은 포만감을 주는 과일을 우선적으로 찾아서 구매하면 된다.

이때 모든 조각 가격은 1로 같기 때문에, 조각당 포만감을 기준으로 내림차순 정렬을 한다.

 

 

for piece_full,fruit_price, fruit_full in fruit_list:

fruit_list를 돌면서 각 요소를 unpacking하여 직접 받아온다.

for _ in range(something)이나 fruit_list[0], fruit_list[1], fruit_list[2]처럼 index로 접근하면 더 오래 걸린다.

 

if MONEY >= fruit_price:
    answer += fruit_full
    MONEY -= fruit_price
        
else:
    answer += MONEY * piece_full
    break

문제를 모르고 있다하더라도, 논리로 이해하면 작성할 수 있는 코드 부분이다.

이미 조각당 포만감 순서대로 내림차순 정렬이 되어있는 상태이다.

즉, 순서대로 이미 최선의 선택을 할 수 있다는 말과 같다.

이때 이 과일을 통째로 살 수 있다면?(MONEY >= fruit_price)

다 사면 된다(MONEY -= fruit_price). 굳이 조각으로 하나하나 계산할 필요가 없다.

그렇게 내가 가진 돈으로 과일을 통째로 사다가, 돈이 부족해지는 경우가 온다(else).

그럼 남은 돈으로 현재 과일 조각을 전부 사면 된다(answer += MONEY * piece_full).

 

다음 과일은 고려하지 않아도 된다.

어차피 수중에 있는 돈으로는 다음 과일은커녕 지금 과일도 다 못 사는 상황이고,

설령 다음 과일을 살 수 있다고 하더라도, 지금 과일의 조각당 포만감이 높다는 사실을 알고 있다.