[백준] 9237번 - 이장님 초대

1. 문제

 

 

2. 코드

n = int(input())
l = list(map(int, input().split()))
l.sort()
max_l = 0

for i in range(n):
    l[i] = l[i] - i
    if l[i] > max_l:
        max_l = l[i]

print(max_l + n + 1)

 

 

3. 풀이

그리디와 정렬을 사용한 문제이다.

자라는 데에 오래 걸리는 나무부터 심었을 때, 모든 나무를 다 심고 나서도 자라는 데에 걸리는 시간을 구한다. l[i] - i

l[i] - i 중 가장 큰 값을 찾고, 거기에 n+1을 해준다.

즉, 나무를 심는데에 걸리는 시간(n) + 나무 다 심고도 다 자라는 데까지 걸리는 시간 (l[i] - i) + 1 인 것이다.