백준 온라인 저지, 그리디 / 4716번: 풍선 (파이썬 / , 백준 플레티넘문제)

문제

전대프연 대회에서 문제를 푼 팀은 풍선을 받게 된다. 풍선은 사람이 직접 달아주기 때문에 자원 봉사자가 필요하다.

풍선은 방 A와 방 B에 보관되어 있다. 대회에 참가한 팀의 수는 총 N개이고, 앉아있는 자리는 서로 다르다. 어떤 팀은 방 A에 가깝고, 어떤 팀은 B에 더 가깝다. 

각 팀에게 달아줘야 하는 풍선의 수와 방 A와 B로부터의 거리가 주어진다. 이때, 모든 풍선을 달아주는데 필요한 이동 거리의 최솟값을 출력한다. 대회에서 풍선을 달아주는 사람은 매우 많고, 풍선은 한 가지 색상을 여러 개 달아준다고 가정한다. 풍선을 달기 위해 이동해야하는 거리는 팀이 A와 B로부터 떨어진 거리와 같다. 풍선을 달아주는 사람은 한 번에 풍선 하나만 들고 이동할 수 있다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 팀의 수 N(1 ≤ N ≤ 1,000)과 방 A와 B에 보관되어있는 풍선의 수 A, B가 주어진다. (0 ≤ A, B ≤ 10,000) 

다음 N개 줄에는 팀에게 달아줘야하는 풍선의 수 K와 방 A로부터 떨어진 거리 D_A, B로부터 떨어진 거리 D_B (0 ≤ D_A, D_B ≤ 1,000)가 주어진다. 풍선이 부족한 경우는 없다. 즉, Σ_i K_i ≤ A+B.

입력의 마지막 줄에는 0이 세 개 주어진다.

출력

각 테스트 케이스에 대해서, 모든 팀에게 풍선을 달아주기 위해 필요한 이동 거리의 최솟값을 한 줄에 하나씩 출력한다. 이때, 풍선을 달아주고 방 A나 B로 돌아오는 거리는 포함하지 않는다. 즉, 방 A와 B에서 팀으로 이동하는 거리만 포함한다.

제한

예제 입력 1

3 15 35
10 20 10
10 10 30
10 40 10
0 0 0

예제 출력 1

300

힌트

W3sicHJvYmxlbV9pZCI6IjQ3MTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ0OGRcdWMxMjAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzgwNFx1YjMwMFx1ZDUwNFx1YzVmMCBcdWIzMDBcdWQ2OGNcdWM1ZDBcdWMxMWMgXHViYjM4XHVjODFjXHViOTdjIFx1ZDQ3YyBcdWQzMDBcdWM3NDAgXHVkNDhkXHVjMTIwXHVjNzQ0IFx1YmMxYlx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1ZDQ4ZFx1YzEyMFx1Yzc0MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjOWMxXHVjODExIFx1YjJlY1x1YzU0NFx1YzhmY1x1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjNzkwXHVjNmQwIFx1YmQwOVx1YzBhY1x1Yzc5MFx1YWMwMCBcdWQ1NDRcdWM2OTRcdWQ1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDQ4ZFx1YzEyMFx1Yzc0MCBcdWJjMjkgQVx1YzY0MCBcdWJjMjkgQlx1YzVkMCBcdWJjZjRcdWFkMDBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWIzMDBcdWQ2OGNcdWM1ZDAgXHVjYzM4XHVhYzAwXHVkNTVjIFx1ZDMwMFx1Yzc1OCBcdWMyMThcdWIyOTQgXHVjZDFkIE5cdWFjMWNcdWM3NzRcdWFjZTAsIFx1YzU0OVx1YzU0NFx1Yzc4OFx1YjI5NCBcdWM3OTBcdWI5YWNcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3NFx1YjJlNC4gXHVjNWI0XHViNWE0IFx1ZDMwMFx1Yzc0MCBcdWJjMjkgQVx1YzVkMCBcdWFjMDBcdWFlNWRcdWFjZTAsIFx1YzViNFx1YjVhNCBcdWQzMDBcdWM3NDAgQlx1YzVkMCBcdWIzNTQgXHVhYzAwXHVhZTVkXHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMzAwXHVjNWQwXHVhYzhjIFx1YjJlY1x1YzU0NFx1YzkxOFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVkNDhkXHVjMTIwXHVjNzU4IFx1YzIxOFx1YzY0MCBcdWJjMjkgQVx1YzY0MCBCXHViODVjXHViZDgwXHVkMTMwXHVjNzU4IFx1YWM3MFx1YjlhY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHViYWE4XHViNGUwIFx1ZDQ4ZFx1YzEyMFx1Yzc0NCBcdWIyZWNcdWM1NDRcdWM4ZmNcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Yzc3NFx1YjNkOSBcdWFjNzBcdWI5YWNcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViMzAwXHVkNjhjXHVjNWQwXHVjMTFjIFx1ZDQ4ZFx1YzEyMFx1Yzc0NCBcdWIyZWNcdWM1NDRcdWM4ZmNcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzQwIFx1YjllNFx1YzZiMCBcdWI5Y2VcdWFjZTAsIFx1ZDQ4ZFx1YzEyMFx1Yzc0MCBcdWQ1NWMgXHVhYzAwXHVjOWMwIFx1YzBjOVx1YzBjMVx1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHVhYzFjIFx1YjJlY1x1YzU0NFx1YzkwMFx1YjJlNFx1YWNlMCBcdWFjMDBcdWM4MTVcdWQ1NWNcdWIyZTQuIFx1ZDQ4ZFx1YzEyMFx1Yzc0NCBcdWIyZWNcdWFlMzAgXHVjNzA0XHVkNTc0IFx1Yzc3NFx1YjNkOVx1ZDU3NFx1YzU3Y1x1ZDU1OFx1YjI5NCBcdWFjNzBcdWI5YWNcdWIyOTQgXHVkMzAwXHVjNzc0IEFcdWM2NDAgQlx1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWI1YThcdWM1YjRcdWM5YzQgXHVhYzcwXHViOWFjXHVjNjQwIFx1YWMxOVx1YjJlNC4gXHVkNDhkXHVjMTIwXHVjNzQ0IFx1YjJlY1x1YzU0NFx1YzhmY1x1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NDAgXHVkNTVjIFx1YmM4OFx1YzVkMCBcdWQ0OGRcdWMxMjAgXHVkNTU4XHViMDk4XHViOWNjIFx1YjRlNFx1YWNlMCBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQzMDBcdWM3NTggXHVjMjE4IE4oMSAmbGU7IE4gJmxlOyAxLDAwMClcdWFjZmMgXHViYzI5IEFcdWM2NDAgQlx1YzVkMCBcdWJjZjRcdWFkMDBcdWI0MThcdWM1YjRcdWM3ODhcdWIyOTQgXHVkNDhkXHVjMTIwXHVjNzU4IFx1YzIxOCBBLCBCXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAgJmxlOyBBLCBCICZsZTsgMTAsMDAwKSZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMzAwXHVjNWQwXHVhYzhjIFx1YjJlY1x1YzU0NFx1YzkxOFx1YzU3Y1x1ZDU1OFx1YjI5NCBcdWQ0OGRcdWMxMjBcdWM3NTggXHVjMjE4IEtcdWM2NDAgXHViYzI5IEFcdWI4NWNcdWJkODBcdWQxMzAgXHViNWE4XHVjNWI0XHVjOWM0IFx1YWM3MFx1YjlhYyBEPHN1Yj5BPFwvc3ViPiwgQlx1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWI1YThcdWM1YjRcdWM5YzQgXHVhYzcwXHViOWFjIEQ8c3ViPkI8XC9zdWI+ICgwICZsZTsgRDxzdWI+QTxcL3N1Yj4sIEQ8c3ViPkI8XC9zdWI+ICZsZTsgMSwwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkNDhkXHVjMTIwXHVjNzc0IFx1YmQ4MFx1Yzg3MVx1ZDU1YyBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LiBcdWM5ODksICZTaWdtYTs8c3ViPmk8XC9zdWI+IEs8c3ViPmk8XC9zdWI+ICZsZTsgQStCLjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1YzEzOCBcdWFjMWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHViYWE4XHViNGUwIFx1ZDMwMFx1YzVkMFx1YWM4YyBcdWQ0OGRcdWMxMjBcdWM3NDQgXHViMmVjXHVjNTQ0XHVjOGZjXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjNzc0XHViM2Q5IFx1YWM3MFx1YjlhY1x1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1ZDQ4ZFx1YzEyMFx1Yzc0NCBcdWIyZWNcdWM1NDRcdWM4ZmNcdWFjZTAgXHViYzI5IEFcdWIwOTggQlx1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2MjRcdWIyOTQgXHVhYzcwXHViOWFjXHViMjk0IFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1Yzk4OSwgXHViYzI5IEFcdWM2NDAgQlx1YzVkMFx1YzExYyBcdWQzMDBcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0IFx1YWM3MFx1YjlhY1x1YjljYyBcdWQzZWNcdWQ1NjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNDcxNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJhbGxvb25zIiwiZGVzY3JpcHRpb24iOiI8cD5BcyB5b3Uga25vdywgYmFsbG9vbnMgYXJlIGhhbmRlZCBvdXQgZHVyaW5nIHRoaXMgY29udGVzdCB0byB0ZWFtcyBhcyB0aGV5IHNvbHZlIHByb2JsZW1zLiBIb3dldmVyLCBpbiB0aGUgcGFzdCB0aGlzIGhhcyBzb21ldGltZXMgcHJlc2VudGVkIGNoYWxsZW5naW5nIGxvZ2lzdGljYWwgcHJvYmxlbXMuPFwvcD5cclxuXHJcbjxwPk9uZSBjb250ZXN0IGhvc3Rpbmcgc2l0ZSBtYWludGFpbmVkIHR3byByb29tcywgQSBhbmQgQiwgZWFjaCBjb250YWluaW5nIGEgc3VwcGx5IG9mIGJhbGxvb25zLiBUaGVyZSB3ZXJlIE4gdGVhbXMgYXR0ZW5kaW5nIHRoZSBjb250ZXN0LCBlYWNoIHNpdHRpbmcgaW4gZGlmZmVyZW50IGxvY2F0aW9ucywgc29tZSBiZWluZyBjbG9zZXIgdG8gcm9vbSBBLCBhbmQgb3RoZXJzIHRvIHJvb20gQi4gR2l2ZW4gdGhlIG51bWJlciBvZiBiYWxsb29ucyBuZWVkZWQgYnkgZWFjaCB0ZWFtIGFuZCBlYWNoIHRlYW1zIGRpc3RhbmNlIGZyb20gcm9vbSBBIGFuZCByb29tIEIsIHdoYXQgaXMgdGhlIG1pbmltdW0gdG90YWwgcG9zc2libGUgZGlzdGFuY2UgdGhhdCBtdXN0IGJlIHRyYXZlbGVkIGJ5IGFsbCBiYWxsb29ucyBhcyB0aGV5IGFyZSBkZWxpdmVyZWQgdG8gdGhlaXIgcmVzcGVjdGl2ZSB0ZWFtcywgYXNzdW1pbmcgdGhleSBhcmUgYWxsb2NhdGVkIGluIGFuIG9wdGltYWwgZmFzaGlvbiBmcm9tIHJvb21zIEEgYW5kIEI/IEZvciB0aGUgcHVycG9zZXMgb2YgdGhpcyBwcm9ibGVtLCBhc3N1bWUgdGhhdCB0aGUgY29udGVzdCBzdGFmZiB3ZXJlIGNoZWFwIGFuZCBvbmx5IGJvdWdodCBvbmUgY29sb3Igb2YgYmFsbG9vbi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZXJlIHdpbGwgYmUgc2V2ZXJhbCB0ZXN0IGNhc2VzIGluIHRoZSBkYXRhIFx1ZmIwMWxlLiBFYWNoIHRlc3QgY2FzZSB3aWxsIGJlZ2luIHdpdGggYSBsaW5lIHdpdGggdGhyZWUgaW50ZWdlcnM6PFwvcD5cclxuXHJcbjxwcmU+XHJcbk4gQSBCPFwvcHJlPlxyXG5cclxuPHA+d2hlcmUgTiBpcyB0aGUgbnVtYmVyIG9mIHRlYW1zICgxICZsZTsgTiAmbGU7IDEsMDAwKSwgYW5kIEEgYW5kIEIgYXJlIHRoZSBudW1iZXIgb2YgYmFsbG9vbnMgaW4gcm9vbXMgQSBhbmQgQiwgcmVzcGVjdGl2ZWx5ICgwICZsZTsgQSwgQiAmbGU7IDEwLDAwMCkuPFwvcD5cclxuXHJcbjxwPk9uIGVhY2ggb2YgdGhlIG5leHQgTiBsaW5lcyB0aGVyZSB3aWxsIGJlIHRocmVlIGludGVnZXJzLCByZXByZXNlbnRpbmcgaW5mb3JtYXRpb24gZm9yIGVhY2ggdGVhbTo8XC9wPlxyXG5cclxuPHByZT5cclxuSyBEPHN1Yj5BPFwvc3ViPiBEPHN1Yj5CPFwvc3ViPjxcL3ByZT5cclxuXHJcbjxwPndoZXJlIEsgaXMgdGhlIHRvdGFsIG51bWJlciBvZiBiYWxsb29ucyB0aGF0IHRoaXMgdGVhbSB3aWxsIG5lZWQsIEQ8c3ViPkE8XC9zdWI+IGlzIHRoZSBkaXN0YW5jZSBvZiB0aGlzIHRlYW0gZnJvbSByb29tIEEsIGFuZCBEPHN1Yj5CPFwvc3ViPiBpcyB0aGlzIHRlYW1zIGRpc3RhbmNlIGZyb20gcm9vbSBCICgwICZsZTsgRDxzdWI+QTxcL3N1Yj4sIEQ8c3ViPkI8XC9zdWI+Jm5ic3A7JmxlOyAxJm5ic3A7MDAwKS4gWW91IG1heSBhc3N1bWUgdGhhdCB0aGVyZSBhcmUgZW5vdWdoIGJhbGxvb25zIC0gdGhhdCBpcywgJlNpZ21hOzxzdWI+aTxcL3N1Yj4mbmJzcDtLPHN1Yj5pPFwvc3ViPiZuYnNwOyZsZTsgQStCLiBUaGUgZGF0YSBcdWZiMDFsZSB3aWxsIGVuZCB3aXRoIGEgbGluZSB3aXRoIHRocmVlIDBzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IGEgc2luZ2xlIGludGVnZXIsIHJlcHJlc2VudGluZyB0aGUgbWluaW11bSB0b3RhbCBkaXN0YW5jZSB0aGF0IG11c3QgYmUgdHJhdmVsZWQgdG8gZGVsaXZlciBhbGwgb2YgdGhlIGJhbGxvb25zLiBDb3VudCBvbmx5IHRoZSBvdXRib3VuZCB0cmlwLCBmcm9tIEEgb3IgQiB0byB0aGUgdGVhbS4gRG9udCBjb3VudCB0aGUgZGlzdGFuY2UgdGhhdCBhIHJ1bm5lciBtdXN0IHRyYXZlbCB0byByZXR1cm4gdG8gcm9vbSBBIG9yIHJvb20gQi4gUHJpbnQgZWFjaCBpbnRlZ2VyIG9uIGl0cyBvd24gbGluZSB3aXRoIG5vIHNwYWNlcy4gRG8gbm90IHByaW50IGFueSBibGFuayBsaW5lcyBiZXR3ZWVuIGFuc3dlcnMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

접근 방법

- 0. 각 자리에 대한 정보를 리스트로 입력받는다.
- 1. 각 앉아있는 자리마다 A와 B 방의 거리를 기준으로 내림차순 정렬한다. (기회비용 고려)
- 2. 리스트를 하나씩 뽑으면서 풍선의 개수와 이동거리를 비교하며 최종적으로 이동한 거리를 출력한다.
- 2-1. 단 이동거리가 같은 경우는 우선순위를 가장 뒤로 미룬다.

코드

# https://www.acmicpc.net/problem/4716
# 접근방법
# 0. 각 자리에 대한 정보를 리스트로 입력받는다.
# 1. 각 앉아있는 자리마다 A와 B 방의 거리를 기준으로 내림차순 정렬한다. (기회비용 고려)
# 2. 리스트를 하나씩 뽑으면서 풍선의 개수와 이동거리를 비교하며 최종적으로 이동한 거리를 출력한다.
# 2-1. 단 이동거리가 같은 경우는 우선순위를 가장 뒤로 미룬다.

while True:
    n, a, b = map(int, input().split())
    if n == a == b == 0:
        break
    array = [list(map(int, input().split())) for _ in range(n)]
    array.sort(key=lambda x: abs(x[1] - x[2]), reverse = True)
    total_distance = 0
    equal_dis = []
    for ballon, distanceA, distanceB in array:
        if distanceA > distanceB:
            if b >= ballon:
                b -= ballon
                total_distance += distanceB * ballon
            else:
                ballon -= b
                total_distance += distanceB * b
                b = 0
                total_distance += distanceA * ballon
        elif distanceA < distanceB:
            if a >= ballon:
                a -= ballon
                total_distance += distanceA * ballon
            else:
                ballon -= a
                total_distance += distanceA * a
                a = 0
                total_distance += distanceB * ballon
        else:
            equal_dis.append([ballon, distanceA, distanceB])
    
    for i in range(len(equal_dis)):
        total_distance += equal_dis[i][0] * equal_dis[i][1]
    
    print(total_distance)