백준 9237번: 이장님 초대 (파이썬)

https://www.acmicpc.net/problem/9237

9237번: 이장님 초대

 

문제

 

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

 

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

 

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

 

입력

 

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

 

출력

 

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

 

풀이

 

시간이 오래 걸리는 모묙부터 심는 것이 가장 최적의 방법일 것이다.

이때 1일부터 시작하고 묘목을 심기 위해 하루가 필요하므로, 해당 묘목이 다 자라는 날 = 1일 + 자라기 위해 필요한 일 수 + 심어지는 순서 + 심는데 걸리는 시간이다.

 

소스 코드

 

n = int(input())
t = list(map(int, input().split()))
t.sort(reverse=True)

for i in range(n):
    t[i] = 1 + t[i] + (i+1)
print(max(t))