문제
농부 상근이는 마당에 심기 위한 나무 묘목 n개를 구입했다. 묘목 하나를 심는데 걸리는 시간은 1일이고, 상근이는 각 묘목이 다 자라는데 며칠이 걸리는지 정확하게 알고 있다.
상근이는 마을 이장님을 초대해 자신이 심은 나무를 자랑하려고 한다. 이장님을 실망시키면 안되기 때문에, 모든 나무가 완전히 자란 이후에 이장님을 초대하려고 한다. 즉, 마지막 나무가 다 자란 다음날 이장님을 초대할 것이다.
상근이는 나무를 심는 순서를 신중하게 골라 이장님을 최대한 빨리 초대하려고 한다. 이장님을 며칠에 초대할 수 있을까?
입력
입력은 두 줄로 이루어져 있다. 첫째 줄에는 묘목의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에는 각 나무가 다 자라는데 며칠이 걸리는지를 나타낸 ti가 주어진다. (1 ≤ ti ≤ 1,000,000)
출력
첫째 줄에 며칠에 이장님을 초대할 수 있는지 출력한다. 답이 여러 가지인 경우에는 가장 작은 값을 출력한다. 묘목을 구입한 날이 1일이다.
N = int(input())
S = list(map(int,input().split()))
S.sort(reverse=True)
result = 0
for i in range(N):
result = max(result,S[i]+i)
print(result+2)풀이 방식
- 배열을 역순으로 나열 (심는데 걸리는 시간은 똑같이 1일인데, 자르는 시간은 묘목마다 다르기 때문에, 가장 빨리 모두 다 심으려면 가장 늦게 걸리는 묘목부터 심어야 한다.)
- (한 묘목이 자라는 데 걸리는 시간 + 그 묘목을 심은 날)이 가장 큰 값이 곧 모든 묘목이 다 자라난 시간이다. 첫번째 예제의 경우 역순으로 심게 되면 4를 첫번째 날 심고 (4+0), 3을 두번째 날 심고 (3+1), 다른 3을 셋째날 심고 (3+2), 마지막으로 2를 (2+4)째날 심는다. 4번째날 심은 2 묘목이 6일째까지 자라고 이 6이 4,4,5보다 크기 때문에 정답이다.
- 묘목을 구입한 날이 1일이고, 이장님을 모든 묘목이 자란 다음날 초대하기 때문에 정답에 2를 더해준다.
Self Refiner