[Python] 백준 9237 - 이장님 초대

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

위 이미지를 클릭하시면 해당 문제 사이트로 연결됩니다.

해결방법

자라는 데에 가장 오래 걸리는 나무부터 가장 빠르게 자라는 나무순으로 배열을 정렬한다. 즉, 내림차순으로 정렬한다는 이야기이다. 나무 한 그루를 심는 데에 꼬박 하루씩이나 걸리니 1일부터 주어진 나무의 수만큼의 일수가 필요하다. 그리고 나무가 자라는 시간까지도 필요하다.

주어진 예제를 통해 이해해보자.

예제 입력 1
4
2 3 4 3

풀이

4그루의 나무를 심는다.

주어진 배열(나무가 자라는 데에 필요한 일 수)을 내림차순으로 정렬하면 [4, 3, 3, 2]가 되겠다.

다 자란 다음날에 이장님을 초대할 것이므로

첫 번째 나무는 1일에 심어지고 자라는 데에 4일이 더 걸리므로 6(5+1)일에,

두 번째 나무는 2일에 심어지고 자라는 데에 3일이 걸리므로 6(5+1)일에,

세 번째 나무는 3일에 심어지고 자라는 데에 3일이 걸리므로 7(6+1)일에,

네 번째 나무는 4일에 심어지고 자라는 데에 2일이 걸리므로 7(6+1)일에 나무를 자랑할 수 있다.

하루라도 빨리 나무를 자랑하고파 모든 나무가 다 자란 다음날에 이장님을 초대하려 한다는 요구와 모든 나무가 완전히 자란 이후에 이장님을 초대하려는 주인공의 요구에 따라 7일에 이장님을 초대할 수 있다.

 

이를 수식으로 표현하면 't 일차 + 자라는 시간 + 1일(다음날)'이다.

그리고 개중에 가장 큰 값이 이 문제의 정답이다.

 

count = int(input()) # 심으려는 나무의 개수
trees = list(map(int,input().split())) # 나무들이 자라는 데에 필요한 일 수
trees.sort(reverse=True) # 내림차순으로 정렬
day = 1 # 나무가 다 자라는 날

for t in range(count):
  full_grow = t+1 + trees[t] + 1
  day = full_grow if full_grow > day else day
print(day) # 이장님 초대하는 날

코드 설명

각 변수들이 의미하는 바는 주석처리를 통해 이야기를 해두었다. 문제의 입력을 보고 보면 무슨 의미인지 한 번에 이해할 것이다. 그러므로 for문 안의 코드들만 설명하겠다.

full_gorw는 나무가 다 자라는 날을 의미한다. 위에서 구한 수식을 '(t+1 일차) + (trees[t] 일) + 1일(다음날)'로 표현한다. t+1일 차인 이유는 t가 0부터 시작하기 때문.

---

원트 성공!