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

• 문제

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

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

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

조건

1.입력은 두 줄로 이루어져 있다. 첫째 줄에는 묘목의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에는 각 나무가 다 자라는데 며칠이 걸리는지를 나타낸 ti가 주어진다. (1 ≤ ti ≤ 1,000,000)
2. 첫째 줄에 며칠에 이장님을 초대할 수 있는지 출력한다. 답이 여러 가지인 경우에는 가장 작은 값을 출력한다. 묘목을 구입한 날이 1일이다.

 

• 코드

# 입력부
tress=int(input());
take_time=list(map(int,input().split()));

# 처리부
result=1; #묘목 구매하는데 1일 소요.
take_time.sort(reverse=True); 

for i in range(1,tress):
    take_time[i]+=i; #나무 심고 나서의 소요시각

result+=max(take_time); #최대 소요시각 더함

# 출력부
print(result+1);#완전히 다 자라면 이장님 초대

 

• 풀이 과정

단순히 나무가 자라는데 걸리는 시간을 내림차순 정리한다.

나무 하나당 심는데 하루가 걸리므로, 생장기간이 긴 나무를 먼저 심는게 총 소요시간이 단축되기 때문이다.

 

즉,

2번째 나무는 생장일+1 일

3번째 나무는 생장일+2 일....

n번째 나무는 생장일+(n-1)일이 걸린다.

이 원리를 for문으로 처리하였다.

 

그럼 이제 리스트에는 나무를 심는 시간과 생장시간이 반영된 값이 들어있다.

 

고로, 리스트에서 가장 큰 값을 하나 선택해 주면 되는 것이다.

 

끝으로,

나무를 구매하는 데 하루, 나무가 다 자란 뒤 이장님을 초대하므로 하루가 더 소요되기 때문에 이틀을 더해주면 문제에서 요구하는 답이 나올 것이다.

 

---

• 여담

오늘은 왜이리 머리가 안 돌아가는 느낌인지 모르겠다.

뭔가 코드가 번뜩 떠오르지 않고, 뭔가 사고 회로가 턱턱 막히는 느낌이다....

 

잠시 쉬다 와야겠다.

 

코드가 이상하거나, 이해되지 않는 부분이 있다면 언제든 댓글 남겨주세요! :)