백준 9237 - 이장님 초대

TechN0·2025년 1월 3일

알고말고 알고리즘

목록 보기

7/22

문제 링크
https://www.acmicpc.net/problem/9237

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	8642	5350	4682	63.666%

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

4
2 3 4 3

예제 출력 1 복사

예제 입력 2 복사

6
39 38 9 35 39 20

예제 출력 2 복사

출처

!https://licensebuttons.net/l/by-sa/3.0/88x31.png

ICPC > Regionals > Europe > Northwestern European Regional Contest > Nordic Collegiate Programming Contest > NCPC 2013 A번

문제를 번역한 사람: baekjoon
문제를 만든 사람: Michał Pilipczuk

알고리즘 분류

풀이

일단 제일 오래걸리는 나무부터 심어야 효율적일 것 같으니

가장 오래 걸리는 나무 순으로 내림차순 정렬 해준다

days.sort(reverse=True)

그 다음

i를 나무를 심는 날짜로 해서 n만큼 반복문을 돌리는데

i번째 날짜 + 나무가 자라는데 걸리는 날짜 를 더해서 max_days에 저장해두고

반복문을 돌면서 가장 큰 값을 찾는다

for i in range(n):
    max_days = max(max_days, i + 1 + days[i])

마지막 나무가 다 자라고 다음날 이장님을 초대해야 하니 마지막에 1을 가산 해준다

print(max_days + 1)

정답

n = int(input())
days = list(map(int, input().split()))

days.sort(reverse=True) # 오래 걸리는것 먼저 심어야 효율적이겠지?
max_days = 0

for i in range(n):
    max_days = max(max_days, i + 1 + days[i])

print(max_days + 1) # 다 자라고 이장님 초대해야 하니 1 더해줘야지지