이장님 초대

출처 : 백준 #9237

시간 제한	메모리 제한
1초	128MB

---

문제

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

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

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

---

입력

입력은 두 줄로 이루어져 있다. 첫째 줄에는 묘목의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에는 각 나무가 다 자라는데 며칠이 걸리는지를 나타낸 ti가 주어진다. (1 ≤ ti ≤ 1,000,000)

---

출력

첫째 줄에 며칠에 이장님을 초대할 수 있는지 출력한다. 답이 여러 가지인 경우에는 가장 작은 값을 출력한다. 묘목을 구입한 날이 1일이다.

---

입출력 예시

예제 입력 1

4
2 3 4 3

예제 출력 1

7

---

예제 입력 2

6
39 38 9 35 39 20

예제 출력 2

42

---

풀이

생각

• 우선 묘목이 다 심어져야 이장님을 초대할 수 있으므로, 묘목이 끝나는 시간에 중점을 두었다.

• 끝나는 시간이 가장 늦은 날짜를 선택 -> greedy

풀이 설명

• 어느 묘목을 먼저심든 상관이 없으므로 우선 .sort(reverse=True)를 통해 역순으로 정렬해주었다.

• for문을 통하여 각 원소에 인덱스 만큼의 시간을 더해주어 묘목이 다 자라는 날짜를 만들어냈다.

• 마지막에 +2를 해준 이유는 묘목을 심기 시작할 때 하루가 걸리고, 모든 묘목이 다 심어져야만 이장님을 초대할 수 있기 때문에 하루 뒤에 초대를 해야한다는 조건 떄문이다.

python code

# 백준 9237번
from sys import stdin

def invite(n, tree):
    tree.sort(reverse=True)

    for i in range(n):  # 끝나는 시간 만들기 (원래 나무가 자랄 시간 + 심기 시작한 시간)
        tree[i] += i

    max_num = max(tree) # 끝나는 시간이 가장 큰 원소 골라내기
    print(tree)
    return max_num+2    # 처음 심을 때 소요되는 1일 + 다 끝나고 나서 이장님을 불러야 하므로 +1




n = int(stdin.readline())
tree = list(map(int, stdin.readline().split()))

result = invite(n, tree)
print(result)