https://school.programmers.co.kr/learn/courses/30/lessons/150368

문제를 예제를 갖고 천천히 다시한번 살펴보자.

// 예제 input 
users = [[40, 10000], [25, 10000]], emoticons =[7000, 9000], 답 = [1, 5400]

먼저 이 행사의 목적은 사용자로 하여금 이모티콘 서비스에 가입하게끔 하려는 것이다.

사용자들을 서비스에 가입시키기 위해 이모티콘을 할인하여 판매한다.

각 사용자들에게는, 이모티콘을 구매하는 기준이 되는 할인율과 서비스에 가입하게 되는 기준이 되는 가격이 있다.

아래로 설명하자면,

1번 사용자는 판매하는 이모티콘들 중에 할인율이 40%이상인 이모티콘만 구매를 하고 총 소비가 10000원 이상이면 구매를 취소하고 서비스에 가입한다.

2번 사용자는 판매하는 이모티콘들 중에 할인율이 25%이상인 이모티콘만 구매를 하고 총 소비가 10000원 이상이면 구매를 취소하고 서비스에 가입한다.

각 이모티콘마다 적용될 수 있는 할인율은 10%, 20%, 30%, 40%이다.

즉 각 이모티콘에 대해서 할인된 경우의 수를 모두 고려한 뒤 각 경우마다 얻게 되는 서비스 가입자수와 이익을 모두 구해서 조건에 맞게 정렬한 뒤 답을 구해주면 된다.

예제를 상태공간트리로 표현하면 이러하다.