1106번: 호텔

Difficulty : Gold V

Problem Description

There are many cities, and Hyeong Taek wants to promote.

Each city has the number of cost and customers.

For example, if city A costs 5 to increase 3 customers, Hyeong Taek can use 15 won to increase 9 customers.

You have to find out the minimum cost to increase the given number of customers.

Input is C and N for the customers and the number of cities.

And N pairs of (cost, customer) will be given in each line.

 

Solution

 

'C' is for the number of customers, 'N' is for the number of cities.

Cost is a list of costs, and count is a list of counts.

'arr' is a temporary list to store inputs.

'ans' is the output list whose index 'I' means the cost to increase 'I' customers.

 

First, store the input pairs into arr.

If I sort 'arr', 'arr' will be sorted by cost because cost comes first.

And divide 'arr' into two lists.

 

13 : Set the initial value of 'ans[i]'. Setted the maximum value to decrease later.

14~16 : If a city has more than 'C' customers and the cost is less than the initial value, change the value.

17~19 : If 'ans[j] + ans[i-j]' is less than 'ans[i]', change the value.

             For example, if 'ans[10]' is 10, 'ans[4]' is 3 and 'ans[6]' is 5, 'ans[10]' can be calculated by adding 3 and 5.

             The range of the loop means that 'ans[4] + ans[6]' equals to 'ans[6] + ans[4]', so I don't need to calculate after                   the middle.