백준 온라인 저지, 그리디 / 1246번: 온라인판매 (파이썬 / 백준 실버문제)

문제 주소: https://www.acmicpc.net/problem/1246

문제

경래는 닭을 기르는데 올 겨울 달걀 풍년으로 함박 웃음을 짓고 있다. 그리고 이 달걀을 영양란으로 둔갑하여 옥션에 판매하려한다.

경래는 총 N개의 달걀이 있고, 그의 잠재적인 고객은 총 M명이다. 그리고 각각의 i번째 고객은 각자 달걀 하나를 P_i 가격 이하로 살 수 있다고 밝혔다.

경래는 영양란이라 속인 죄책감에 한 고객에게 두 개 이상의 달걀은 팔지 않기로 하였다. 하지만 위의 규칙 하에 수익은 최대로 올리고 싶기에 얼마로 팔지 고민하고 있다. 즉, A가격에 달걀을 판다고 하면 P_i가 A가격보다 크거나 같은 모든 고객은 달걀을 산다는 뜻이다. (물론 달걀 총 수량을 초과하여 팔 수 는 없다)

문제는 이러한 경래를 도와 최대 수익을 올릴 수 있는 달걀의 가장 낮은 가격을 책정하는 것이다.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 1,000)과 M(1 ≤ M ≤ 1,000)이 입력된다. 둘째 줄부터 M+1번째 줄까지 i+1번째 줄에는 P_i(1 ≤ P_i ≤ 1,000,000)가 입력된다.

출력

첫째 줄에 경래가 책정한 가격과 이 가격으로 올릴 수 있는 수익을 출력한다.

제한

예제 입력 1

5 4
2
8
10
7

예제 출력 1

7 21

힌트

W3sicHJvYmxlbV9pZCI6IjEyNDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2MjhcdWI3N2NcdWM3NzggXHVkMzEwXHViOWU0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWFjYmRcdWI3OThcdWIyOTQgXHViMmVkXHVjNzQ0IFx1YWUzMFx1Yjk3NFx1YjI5NFx1YjM3MCBcdWM2MmMgXHVhY2E4XHVjNmI4IFx1YjJlY1x1YWM0MCBcdWQ0OGRcdWIxNDRcdWM3M2NcdWI4NWMgXHVkNTY4XHViYzE1IFx1YzZjM1x1Yzc0Y1x1Yzc0NCBcdWM5ZDNcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHVjNzc0IFx1YjJlY1x1YWM0MFx1Yzc0NCBcdWM2MDFcdWM1OTFcdWI3ODBcdWM3M2NcdWI4NWMgXHViNDU0XHVhYzExXHVkNTU4XHVjNWVjIFx1YzYyNVx1YzE1OFx1YzVkMCBcdWQzMTBcdWI5ZTRcdWQ1NThcdWI4MjRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNiZFx1Yjc5OFx1YjI5NCBcdWNkMWQgTlx1YWMxY1x1Yzc1OCBcdWIyZWNcdWFjNDBcdWM3NzQgXHVjNzg4XHVhY2UwLCBcdWFkZjhcdWM3NTggXHVjN2EwXHVjN2FjXHVjODAxXHVjNzc4IFx1YWNlMFx1YWMxZFx1Yzc0MCBcdWNkMWQgTVx1YmE4NVx1Yzc3NFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YWMwMVx1YWMwMVx1Yzc1OCBpXHViYzg4XHVjOWY4IFx1YWNlMFx1YWMxZFx1Yzc0MCBcdWFjMDFcdWM3OTAgXHViMmVjXHVhYzQwIFx1ZDU1OFx1YjA5OFx1Yjk3YyBQPHN1Yj5pPFwvc3ViPiBcdWFjMDBcdWFjYTkgXHVjNzc0XHVkNTU4XHViODVjIFx1YzBiNCBcdWMyMTggXHVjNzg4XHViMmU0XHVhY2UwIFx1YmMxZFx1ZDYxNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhY2JkXHViNzk4XHViMjk0IFx1YzYwMVx1YzU5MVx1Yjc4MFx1Yzc3NFx1Yjc3YyBcdWMxOGRcdWM3NzggXHVjOGM0XHVjYzQ1XHVhYzEwXHVjNWQwIFx1ZDU1YyBcdWFjZTBcdWFjMWRcdWM1ZDBcdWFjOGMgXHViNDUwIFx1YWMxYyBcdWM3NzRcdWMwYzFcdWM3NTggXHViMmVjXHVhYzQwXHVjNzQwIFx1ZDMxNFx1YzljMCBcdWM1NGFcdWFlMzBcdWI4NWMgXHVkNTU4XHVjNjAwXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHVjNzA0XHVjNzU4IFx1YWRkY1x1Y2U1OSBcdWQ1NThcdWM1ZDAgXHVjMjE4XHVjNzc1XHVjNzQwIFx1Y2Q1Y1x1YjMwMFx1Yjg1YyBcdWM2MmNcdWI5YWNcdWFjZTAgXHVjMmY2XHVhZTMwXHVjNWQwIFx1YzViY1x1YjljOFx1Yjg1YyBcdWQzMTRcdWM5YzAgXHVhY2UwXHViYmZjXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjOTg5LCBBXHVhYzAwXHVhY2E5XHVjNWQwIFx1YjJlY1x1YWM0MFx1Yzc0NCBcdWQzMTBcdWIyZTRcdWFjZTAgXHVkNTU4XHViYTc0IFA8c3ViPmk8XC9zdWI+XHVhYzAwIEFcdWFjMDBcdWFjYTlcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCZuYnNwO1x1YmFhOFx1YjRlMCBcdWFjZTBcdWFjMWRcdWM3NDAgXHViMmVjXHVhYzQwXHVjNzQ0IFx1YzBiMFx1YjJlNFx1YjI5NCBcdWI3M2JcdWM3NzRcdWIyZTQuIChcdWJiM2NcdWI4NjAgXHViMmVjXHVhYzQwIFx1Y2QxZCBcdWMyMThcdWI3YzlcdWM3NDQgXHVjZDA4XHVhY2ZjXHVkNTU4XHVjNWVjIFx1ZDMxNCBcdWMyMTggXHViMjk0IFx1YzVjNlx1YjJlNCk8XC9wPlxyXG5cclxuPHA+XHViYjM4XHVjODFjXHViMjk0IFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWFjYmRcdWI3OThcdWI5N2MgXHViM2M0XHVjNjQwIFx1Y2Q1Y1x1YjMwMCBcdWMyMThcdWM3NzVcdWM3NDQgXHVjNjJjXHViOWI0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViMmVjXHVhYzQwXHVjNzU4IFx1YWMwMFx1YzdhNSBcdWIwYWVcdWM3NDAgXHVhYzAwXHVhY2E5XHVjNzQ0IFx1Y2M0NVx1YzgxNVx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzIxOCBOKDEgJmxlOyBOICZsZTsgMSwwMDApXHVhY2ZjIE0oMSAmbGU7IE0gJmxlOyAxLDAwMClcdWM3NzQgXHVjNzg1XHViODI1XHViNDFjXHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE0rMVx1YmM4OFx1YzlmOCBcdWM5MDRcdWFlNGNcdWM5YzAgaSsxXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBQPHN1Yj5pPFwvc3ViPigxICZsZTsgUDxzdWI+aTxcL3N1Yj4mbmJzcDsmbGU7IDEsMDAwLDAwMClcdWFjMDAgXHVjNzg1XHViODI1XHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhY2JkXHViNzk4XHVhYzAwIFx1Y2M0NVx1YzgxNVx1ZDU1YyBcdWFjMDBcdWFjYTlcdWFjZmMgXHVjNzc0IFx1YWMwMFx1YWNhOVx1YzczY1x1Yjg1YyBcdWM2MmNcdWI5YjQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMyMThcdWM3NzVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjEyNDYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHb2luZyBPbmNlLCBHb2luZyBUd2ljZSwgR29uZSEiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBjb3dzJiMzOTsgc2xpbW1pbmcgZGlldCBoYXMgbGVmdCBGYXJtZXIgSm9obiB3aXRoIGV4dHJhIGhheSBzbyBoZSBoYXMgZGVjaWRlZCB0byBob2xkIGFuIGF1Y3Rpb24gdG8gcmVkdWNlIGhpcyBpbnZlbnRvcnkuIEhlIGhhcyBOICgxICZsdDs9IE4gJmx0Oz0gMSwwMDApIGlkZW50aWNhbCBsb3RzIChlYWNoIG9mIGFib3V0IDEwMCBiYWxlcykgb2YgaGF5OyBoaXMgcG90ZW50aWFsIGN1c3RvbWVycyBjb21wcmlzZSBNICgxICZsdDs9IE0gJmx0Oz0gMSwwMDApIG90aGVyIGZhcm1lcnMgaW4gdGhlIGFyZWEuPFwvcD5cclxuXHJcbjxwPkVhY2ggZmFybWVyIGkgdGVsbHMgRmFybWVyIEpvaG4gaG93IG11Y2ggaGUgaXMgd2lsbGluZyB0byBwYXkgUF9pICgxICZsdDs9IFBfaSAmbHQ7PSAxLDAwMCwwMDApIGZvciBhIGxvdCBvZiBoYXkuIEVhY2ggb2YgdGhlIGZhcm1lcnMgd2lzaGVzIHRvIHB1cmNoYXNlIGEgc2luZ2xlIGxvdCBvZiBoYXkuPFwvcD5cclxuXHJcbjxwPlRvIG1ha2Ugc3VyZSB0aGUgb3RoZXIgZmFybWVycyBkbyBub3QgZ2V0IGplYWxvdXMgb2YgZWFjaCBvdGhlciwgRmFybWVyIEpvaG4gZGVjaWRlcyB0aGF0IGhlIG11c3Qgc2VsbCB0aGUgbG90cyBvZiBoYXkgYXQgYSBmaXhlZCBwcmljZSB0byBlYWNoIGN1c3RvbWVyIHdobyBpcyB3aWxsaW5nIHRvIHBheSBhdCBsZWFzdCB0aGF0IHByaWNlOyB0aGUgcmVzdCB3aWxsIGRlY2xpbmUgdGhlIHB1cmNoYXNlLjxcL3A+XHJcblxyXG48cD5IZWxwIEZhcm1lciBKb2huIGRldGVybWluZSB0aGUgc21hbGxlc3QgcHJpY2UgaGUgc2hvdWxkIHNldCBvbiBhIGxvdCBvZiBoYXkgdG8gbWF4aW1pemUgdGhlIGFtb3VudCBvZiBtb25leSBoZSBtYWtlcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPiogTGluZSAxOiBUd28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBOIGFuZCBNPFwvcD5cclxuXHJcbjxwPiogTGluZXMgMi4uTSsxOiBMaW5lIGkrMSBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyOiBQX2k8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD4qIExpbmUgMTogVHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogdGhlIHNtYWxsZXN0IHByaWNlIHRoYXQgRmFybWVyIEpvaG4gc2hvdWxkIGNob29zZSB0byBtYXhpbWl6ZSBoaXMgcmV2ZW51ZSBhbmQgdGhlIGFtb3VudCBvZiBtb25leSBoZSB0YWtlcyBpbi48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

접근 방법

- 가격을 내림차순으로 정렬한 뒤 각 가격 당 얼마씩 수익을 얻을 수 있는지 체크하여 최대 수익이나는 가격과 수익을 출력한다.

코드

# https://www.acmicpc.net/problem/1246
# 접근 방법
# 가격을 내림차순으로 정렬한 뒤 각 가격 당 얼마씩 수익을 얻을 수 있는지 체크하여 최대 수익이나는 가격과 수익을 출력한다.
n, m = map(int,input().split())
price = [int(input()) for _ in range(m)]
price.sort(reverse = True)
result = []
for i in range(m):
    result.append([price[i], price[i]*min(i+1, n)])
result.sort(key=lambda x:x[1], reverse=True)
print(result[0][0], result[0][1])