[그리디] 백준 #9237 이장님 초대 - Python

🗂️ 문제

 

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

 

 

💡 접근법

최대한 빠르게 모든 묘목을 심고 다 자라게하기 위해서는 자라는 데 오래 걸리는 묘목부터 심어야 한다.따라서 묘목이 자라는 기간을 내림차순으로 정렬한다.

 

묘목 하나를 심는 데 1일이 소요된다. 이 말은 묘목은 하루에 하나만 심을 수 있다는 말로 해석된다.

따라서 묘목을 구입한 1일부터 바로 묘목을 심도록 하자.

또한 묘목을 심은 날짜에 묘목이 자라는 데 걸리는 기간을 더한다면 해당 묘목이 모두 자라는 날짜를 구할 수 있다.

 

예시를 들어 살펴보자.

1일에 첫 번째 묘목을 심는다. 이때 첫 번째 묘목이 자라는 데 4일이 걸린다면, 해당 묘목은 5일까지 모두 자란다.

2일에 두 번째 묘목을 심는다. 이때 두 번째 묘목이 자라는 데 3일이 걸린다면, 해당 묘목은 5일까지 모두 자란다.

 

즉, 위와 같은 방식으로 각각의 묘목이 모두 자라는 날짜를 구하고, 그 중 최댓값에 +1한 날짜가 이장님을 초대할 수 있는 날짜이다.

 

😎 내 코드

import sys

N = int(sys.stdin.readline())
trees = list(map(int, sys.stdin.readline().split()))

trees.sort(reverse=True)

days = 1
growing_days = []
for tree in trees:
    growing_days.append(days + tree)  # 묘목이 모두 자라는 날짜
    days += 1

print(max(growing_days) + 1)  # 이장님 초대 날짜

 

✅ 정답 확인