알고리즘 정복하기!/백준 문제풀이

백준 9237번 Python / Greedy

by seokii 2022. 2. 16.
728x90
반응형

문제 링크

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

 

9237번: 이장님 초대

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

www.acmicpc.net

 

풀이

n = int(input())
t = list(map(int, input().split()))
t.sort(reverse=True)

answer = 1 + t[0] + 1
for i in range(1, len(t)):
    if 1 + i + t[i] + 1 > answer:
        answer = 1 + i + t[i] + 1

print(answer)

묘목을 빠르게 심어 가장 빠른 날 이장님을 뵙는 것이 목표인 문제입니다.

 

묘목이 자라는 데 오래걸리는 순으로 심는 것이 작업을 마치는 데 가장 빠르기 때문에

묘목 성장 시간을 입력 받은 리스트 t에 대해 내림차순으로 정렬합니다.

 

첫 answer변수의 선언은 1 + t[0] + 1로 지정했습니다.

첫 번째 1은 1일을 의미, t[0]는 묘목이 다 자라는데 걸리는 시간을 의미, 마지막 1은 그 다음날 이장님을 뵙기 때문에 더해주었습니다.

 

그리고 간단한 for문을 통해 답을 구했습니다.

리스트의 1번째부터(0번째는 첫 선언때 지정했음) 마지막까지 for문을 돌렸는데,

1 + i + t[i] + 1의 값이 기존에 지정했던 answer보다 클 경우 answer 값으로 지정해주었습니다.

계산식의 의미는 기본적으로 첫 answer 변수 선언과 방식이 같으며 추가된 i는 지금까지 흘러간 시간을 추가한 것입니다.

 

 

728x90
반응형

댓글