📌문제
이웃 농장의 소가 길을 마구잡이로 건너는 것에 진절머리가 난 존은 극단의 결정을 내린다. 농장 둘레에 매우 큰 울타리를 짓는 것이다. 이렇게 하면 근처 농장 출신의 소가 들어올 일이 거의 없다. 이 일로 주변 소들이 분개하였다. 친구네 집에 놀러 갈 수 없을 뿐만 아니라, 매년 참가하던 국제 젖 짜기 올림피아드에도 올해는 참가할 수 없게 되었기 때문이다.
이웃 농장의 소 중 존의 농장에 방문할 수 있는 소가 조금 있긴 하지만, 그들도 안심할 수 있는 건 아니다. 존의 농장에 들어가는 문은 하나밖에 없고, 그 문을 통과하려면 감시관의 길고 긴 검문을 받아야 한다. 여러 마리의 소가 한 번에 들어가려고 하면 줄이 그 만큼 길어진다.
N마리의 소가 이 농장에 방문하러 왔다. 소가 도착한 시간과 검문받는 데 걸리는 시간은 소마다 다르다. (물론 같을 수도 있다.) 두 소가 동시에 검문을 받을 수는 없다. 예를 들어, 한 소가 5초에 도착했고 7초 동안 검문을 받으면, 8초에 도착한 그 다음 소는 12초까지 줄을 서야 검문을 받을 수 있다.
모든 소가 농장에 입장하려면 얼마나 걸리는 지 구해보자.
입력
첫 줄에 100 이하의 양의 정수 N이 주어진다. 다음 N줄에는 한 줄에 하나씩 소의 도착 시각과 검문 시간이 주어진다. 각각 1,000,000 이하의 양의 정수이다.
출력
모든 소가 농장에 입장하는 데 걸리는 최소 시간을 출력한다.
예제 입력
3
2 1
8 3
5 7예제 출력
15💡Idea
ATM 문제처럼 그리디로 풀면 되는 문제입니다.
모든 소🐄가 농장에 입장하는 데 걸리는 최소 시간을 구하려면 먼저 온 소부터 빨리 입장시키면 됩니다.
같이 도착한 소가 여러 마리인 경우, 소들이 검문받는 데에 걸리는 시간은 고려하지 않아도 됩니다. 어차피 총 걸리는 시간은 순서에 상관없이 동일하기 때문입니다.
💻코드
- ⏰ 시간 : 68 ms / 메모리 : 30840 KB
import sys
input = sys.stdin.readline
cows = [list(map(int, input().split())) for _ in range(int(input()))] # [도착 시각, 검문 시간]
cows.sort() # 도착 시각 기준 정렬
time = 0 # 소가 입장하는 데에 걸리는 시간
for a, b in cows:
if a <= time:
time +=b
else: time = a + b
print(time)먼저 도착한 소들을 먼저 입장시키기 위하여 소들의 도착 시각을 기준으로 오름차순 정렬을 먼저 해줍니다.
그리고 정렬된 소들을 입장시키기 시작합니다.
각 소들의 도착 시각을 확인하면서, 만약 앞의 소들이 전부 입장했을 때 소가 도착해있다면 바로 입장시키면서 time에 검문 시간을 더해주면 됩니다.
만약 앞의 소들이 전부 입장했지만 아직 다음 소의 도착 시각이 되지 않았다면, 다음 소의 도착 시각과 검문 시간을 더해준 값으로 time의 값을 대체해줍니다.
