[백준] 9237 이장님 초대 (Python 파이썬)

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

9237번: 이장님 초대

문제 설명

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

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

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

---

풀이 과정

나무가 모두 자라는데 걸리는 시간은 정해져 있고, 나무의 심는 순서는 내가 마음대로 정할 수 있는 상황이다.

최대한 빨리 나무들을 모두 길러야 하기 때문에 자라는데 오래 걸리는 나무부터 심어야 할 것이다.

 

그래서, 나무들의 일수를 먼저 내림차순으로 정렬을 한다.

 

그리고, 마지막에 자라는 나무를 찾아야 한다.

예를 들어, 4 3 2 2 나무를 심게 되면

4일짜리 나무가 가장 오래 걸리므로 4일짜리 나무를 처음 심게 되지만,

 

처음 4일짜리 나무가 모두 자라나는 동안 마지막의 2일짜리 나무는 모두 자라지 못한다.

 

따라서, 나무를 심는데 걸리는 일수의 최댓값을 저장해주며 이를 필요할 때 마다 바꿔주는 과정이 필요하다.

 

4일짜리 나무를 처음 심은 날을 1일이라고 하면,

이 나무가 모두 자라는 일은 5일이 될 것이며 이 때, 4번째로 심은 2일짜리 나무는 하루가 더 필요한 상황이다.

 

그래서 max_days < i + days[i] 의 조건문을 이용해 최종적으로 자라나는 나무를 탐색한 후에

max값을 갱신하면 된다.

 

그리고 마지막에 +2일을 하여, 처음 심는 1일과 마지막 1일을 더해주면 된다.

(이장님은 다음날 초대하기로 하였으며, 나무를 심는데는 1일이 걸리므로 심는날 1일을 제외해야 한다.)

n = int(input())
days = list(map(int, input().split()))

days.sort(reverse=True)

max_days = days[0]

if n == 1:
    print(n + 2)
else:
    for i in range(1, n):
        if max_days < (i + days[i]):
            max_days = i + days[i]

    result = max_days + 2
    print(result)

 

https://github.com/HongEunho

HongEunho - Overview

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !