[그리디/Greedy] 백준 14469 소가 길을 건너간 이유 3 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

14469번: 소가 길을 건너간 이유 3

 

 

 

2. 문제 풀이

 소들의 도착시간, 검문에 필요한 시간이 주어집니다. 검문은 1마리씩 가능하며, 모든 소들을 입장시키는 데에 필요한 최소 시간을 구해야 합니다.

 

2022.01.26 - [Algorithm] - [Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결

[Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결

 그리디 알고리즘으로, 도착 순서대로 소를 입장시키면 됩니다. 굳이 검문에 필요한 시간은 고려하지 않아도 됩니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
N = int(input())
cow = []
for _ in range(N):
    cow.append(list(map(int, input().split())))  # start, duration

# 정렬
cow.sort()

# 시간 계산
res = 0
for start, duration in cow:
    # 도착시간까지 시간이 남았으면, 기다렸다가 입장
    if res < start:
        res = start+duration

    # 검문 중인 소가 있다면 기다렸다가 바로 입장
    else:
        res += duration
print(res)