백준 온라인 저지, 그리디 / 9237번: 이장님초대 (파이썬 / , 백준 실버문제)

문제

농부 상근이는 마당에 심기 위한 나무 묘목 n개를 구입했다. 묘목 하나를 심는데 걸리는 시간은 1일이고, 상근이는 각 묘목이 다 자라는데 며칠이 걸리는지 정확하게 알고 있다.

상근이는 마을 이장님을 초대해 자신이 심은 나무를 자랑하려고 한다. 이장님을 실망시키면 안되기 때문에, 모든 나무가 완전히 자란 이후에 이장님을 초대하려고 한다. 즉, 마지막 나무가 다 자란 다음날 이장님을 초대할 것이다.

상근이는 나무를 심는 순서를 신중하게 골라 이장님을 최대한 빨리 초대하려고 한다. 이장님을 며칠에 초대할 수 있을까?

입력

입력은 두 줄로 이루어져 있다. 첫째 줄에는 묘목의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에는 각 나무가 다 자라는데 며칠이 걸리는지를 나타낸 t_i가 주어진다. (1 ≤ t_i ≤ 1,000,000)

출력

첫째 줄에 며칠에 이장님을 초대할 수 있는지 출력한다. 답이 여러 가지인 경우에는 가장 작은 값을 출력한다. 묘목을 구입한 날이 1일이다.

제한

예제 입력 1

4
2 3 4 3

예제 출력 1

7

예제 입력 2

6
39 38 9 35 39 20

예제 출력 2

42

힌트

W3sicHJvYmxlbV9pZCI6IjkyMzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NzRcdWM3YTVcdWIyZDggXHVjZDA4XHViMzAwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIxOGRcdWJkODAgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjljOFx1YjJmOVx1YzVkMCBcdWMyZWNcdWFlMzAgXHVjNzA0XHVkNTVjIFx1YjA5OFx1YmIzNCBcdWJiMThcdWJhYTkgblx1YWMxY1x1Yjk3YyBcdWFkNmNcdWM3ODVcdWQ1ODhcdWIyZTQuIFx1YmIxOFx1YmFhOSBcdWQ1NThcdWIwOThcdWI5N2MgXHVjMmVjXHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDAgMVx1Yzc3Y1x1Yzc3NFx1YWNlMCwgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YWMwMSBcdWJiMThcdWJhYTlcdWM3NzQgXHViMmU0IFx1Yzc5MFx1Yjc3Y1x1YjI5NFx1YjM3MCBcdWJhNzBcdWNlNjBcdWM3NzQgXHVhYzc4XHViOWFjXHViMjk0XHVjOWMwIFx1YzgxNVx1ZDY1NVx1ZDU1OFx1YWM4YyBcdWM1NGNcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViOWM4XHVjNzQ0IFx1Yzc3NFx1YzdhNVx1YjJkOFx1Yzc0NCBcdWNkMDhcdWIzMDBcdWQ1NzQgXHVjNzkwXHVjMmUwXHVjNzc0IFx1YzJlY1x1Yzc0MCBcdWIwOThcdWJiMzRcdWI5N2MgXHVjNzkwXHViNzkxXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHVjN2E1XHViMmQ4XHVjNzQ0IFx1YzJlNFx1YjlkZFx1YzJkY1x1ZDBhNFx1YmE3NCBcdWM1NDhcdWI0MThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWJhYThcdWI0ZTAgXHViMDk4XHViYjM0XHVhYzAwIFx1YzY0NFx1YzgwNFx1ZDc4OCBcdWM3OTBcdWI3ODAgXHVjNzc0XHVkNmM0XHVjNWQwIFx1Yzc3NFx1YzdhNVx1YjJkOFx1Yzc0NCBcdWNkMDhcdWIzMDBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM5ODksIFx1YjljOFx1YzljMFx1YjljOSBcdWIwOThcdWJiMzRcdWFjMDAgXHViMmU0IFx1Yzc5MFx1Yjc4MCBcdWIyZTRcdWM3NGNcdWIwYTAgXHVjNzc0XHVjN2E1XHViMmQ4XHVjNzQ0IFx1Y2QwOFx1YjMwMFx1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWIwOThcdWJiMzRcdWI5N2MgXHVjMmVjXHViMjk0IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWMyZTBcdWM5MTFcdWQ1NThcdWFjOGMgXHVhY2U4XHViNzdjIFx1Yzc3NFx1YzdhNVx1YjJkOFx1Yzc0NCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViZTY4XHViOWFjIFx1Y2QwOFx1YjMwMFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YzdhNVx1YjJkOFx1Yzc0NCBcdWJhNzBcdWNlNjBcdWM1ZDAgXHVjZDA4XHViMzAwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3NDRcdWFlNGM/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHViNDUwIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmIxOFx1YmFhOVx1Yzc1OCBcdWMyMTggTiAoMSAmbGU7IE4gJmxlOyAxMDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YjA5OFx1YmIzNFx1YWMwMCBcdWIyZTQgXHVjNzkwXHViNzdjXHViMjk0XHViMzcwIFx1YmE3MFx1Y2U2MFx1Yzc3NCBcdWFjNzhcdWI5YWNcdWIyOTRcdWM5YzBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4IHQ8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyB0PHN1Yj5pPFwvc3ViPiAmbGU7IDEsMDAwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmE3MFx1Y2U2MFx1YzVkMCBcdWM3NzRcdWM3YTVcdWIyZDhcdWM3NDQgXHVjZDA4XHViMzAwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWIyZjVcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWJiMThcdWJhYTlcdWM3NDQgXHVhZDZjXHVjNzg1XHVkNTVjIFx1YjBhMFx1Yzc3NCAxXHVjNzdjXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjkyMzciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQbGFudGluZyBUcmVlcyIsImRlc2NyaXB0aW9uIjoiPHA+RmFybWVyIEpvbiBoYXMgcmVjZW50bHkgYm91Z2h0IG4gdHJlZSBzZWVkbGluZ3MgdGhhdCBoZSB3YW50cyB0byBwbGFudCBpbiBoaXMgeWFyZC4gSXQgdGFrZXMgMSBkYXkgZm9yIEpvbiB0byBwbGFudCBhIHNlZWRsaW5nLCBhbmQgZm9yIGVhY2ggdHJlZSBKb24ga25vd3MgZXhhY3RseSBpbiBob3cgbWFueSBkYXlzIGFmdGVyIHBsYW50aW5nIGl0IGdyb3dzIHRvIGZ1bGwgbWF0dXJpdHkuIEpvbiB3b3VsZCBhbHNvIGxpa2UgdG8gdGhyb3cgYSBwYXJ0eSBmb3IgaGlzIGZhcm1lciBmcmllbmRzLCBidXQgaW4gb3JkZXIgdG8gaW1wcmVzcyB0aGVtIGhlIHdvdWxkIGxpa2UgdG8gb3JnYW5pemUgdGhlIHBhcnR5IG9ubHkgYWZ0ZXIgYWxsIHRoZSB0cmVlcyBoYXZlIGdyb3duLiBNb3JlIHByZWNpc2VseSwgdGhlIHBhcnR5IGNhbiBiZSBvcmdhbml6ZWQgYXQgZWFybGllc3Qgb24gdGhlIG5leHQgZGF5IGFmdGVyIHRoZSBsYXN0IHRyZWUgaGFzIGdyb3duIHVwLjxcL3A+XHJcblxyXG48cD5IZWxwIEpvbiB0byBcdWZiMDFuZCBvdXQgd2hlbiBpcyB0aGUgZWFybGllc3QgZGF5IHdoZW4gdGhlIHBhcnR5IGNhbiB0YWtlIHBsYWNlLiBKb24gY2FuIGNob29zZSB0aGUgb3JkZXIgb2YgcGxhbnRpbmcgdGhlIHRyZWVzIGFzIGhlIGxpa2VzLCBzbyBoZSB3YW50cyB0byBwbGFudCB0aGUgdHJlZXMgaW4gc3VjaCBhIHdheSB0aGF0IHRoZSBwYXJ0eSB3aWxsIGJlIGFzIHNvb24gYXMgcG9zc2libGUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgdHdvIGxpbmVzLiBUaGUgXHVmYjAxcnN0IGxpbmUgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwMCAwMDApIGRlbm90aW5nIHRoZSBudW1iZXIgb2Ygc2VlZGxpbmdzLiBUaGVuIGEgbGluZSB3aXRoIE4gaW50ZWdlcnMgdDxzdWI+aTxcL3N1Yj4gZm9sbG93cyAoMSAmbGU7IHQ8c3ViPmk8XC9zdWI+ICZsZTsgMSAwMDAgMDAwKSwgd2hlcmUgdGkgZGVub3RlcyB0aGUgbnVtYmVyIG9mIGRheXMgaXQgdGFrZXMgZm9yIHRoZSBpdGggdHJlZSB0byBncm93LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdSBwcm9ncmFtIHNob3VsZCBvdXRwdXQgZXhhY3RseSBvbmUgbGluZSBjb250YWluaW5nIG9uZSBpbnRlZ2VyLCBkZW5vdGluZyB0aGUgZWFybGllc3QgZGF5IHdoZW4gdGhlIHBhcnR5IGNhbiBiZSBvcmdhbml6ZWQuIFRoZSBkYXlzIGFyZSBudW1iZXJlZCAxLCAyLCAzLCAuLi4gYmVnaW5uaW5nIGZyb20gdGhlIGN1cnJlbnQgbW9tZW50LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

접근 방법

- 내림차순으로 정렬해 시간을 계산한다.

코드

# https://www.acmicpc.net/problem/9237
# 접근 방법
# 내림차순으로 정렬해 시간을 계산한다.
n = int(input())
arr = list(map(int, input().split()))
arr.sort(reverse=True)
result = 0
for i in range(n):
    result = max(result, arr[i] + i + 1)
print(result + 1)