[Python] BOJ(백준) 9237번 - 이장님 초대

1. 링크

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

2. 난이도(solved.ac 참고)

실버5

3. 풀이

	n = int(input())
	t = list(map(int, input().split()))
	t.sort(reverse=True)
	max_day = 0
	for i in range(n):
	candidate = t[i] + i + 1
	if candidate > max_day:
	max_day = candidate
	print(max_day + 1)

view raw 이장님초대.py hosted with ❤ by GitHub

좀 허무했다. 처음에 내가 너무 어렵게 생각했는데, 이게 실버5가 맞나..? 라는 생각이 들어서 일단 접어뒀다가 다시 풀고 금방 맞았다.

이 문제에서의 핵심은, 총 걸리는 시간은 배열 내 최대값 + 그 인덱스의 값이기 때문에, 큰 값을 가장 앞에 둬야 된다는 것이다. 큰 값이 뒤에 있다면, 이미 인덱스가 많이 증가한 상태이기 때문에 결국 최종 걸리는 시간은 더 길어지게 된다.

t 배열에 각자 다 자라는데 며칠이 걸리는지에 대한 값을 넣었고, 그 값을 내림차순으로 정렬했다. 그렇게 되면, 다 자라는 데 오래 걸리는 묘목을 앞 순서에 배치시켜서 묘목이 자라는 데 걸리는 시간 외에, 그 묘목을 심기까지의 시간은 최소화시킬 수 있다.

for문을 돌면서, 첫 묘목을 심는 날이 1일이기 때문에 배열 + 인덱스에 1을 더해줬고, 모든 묘목이 자라고 난 다음 날에 이장님을 초대하므로 1을 더해주는 값을 최종적으로 출력했다.