[Python] 9237번 이장님 초대

✏️ 문제

 

문제 파악

일단 첫 날을 1일로 계산하고 이장님을 다 자라고 다음날에 부르므로 각각 +1 씩 해준다. 

그 후 다 심을 때까지의 날짜가 필요하므로 n개를 다 심으면 (n-1)일 후이므로 날짜에 (n-1)을 더해준다.

그 후 내림차순 정렬하여 맨 앞에 있는 배열 요소가 0이 될 때까지 날짜가 필요하므로 배열[0]을 더해준다.

 

이때 처음 배열에 (n-1)일 후의 남은 날짜를 넣으려고 할 때 for 반복문을 2개 사용하면 시간 초과가 생기므로 이를 넣기 쉽게 하기 위해서 내림차순 정렬을 해주었다.

 

알고리즘

• 그리디 알고리즘
• 정렬

 

 

코드

import sys
input = sys.stdin.readline

n = int(input())
tree = list(map(int, input().split()))
day = 1

tree.sort()
for i in range(1, n):
  day += 1
  tree[i] -= i

tree.sort(reverse=True)
day += tree[0] + 1
print(day)