[Python] 14469번 소가 길을 건너간 이유 3

✏️ 문제

 

문제 파악

나는 먼저 정렬을 한 후 제일 처음에 온 소는 무조건 프리패스니까 소요시간에 먼저 더해줬다.

그 후에는 두 가지 경우로 나눠서 생각했다. 처음에 온 소가 검문이 끝난 시간 T을 기준으로 

1. T <= 다음 소의 도착 시간이라면 다음 소의 도착 시간까지 소요시간이 되어야 하므로
   → 소요시간 += (다음 소의 도착 시간 - 소요시간) + 다음 소의 검문 시간
2. T > 다음 소의 도착 시간이라면 다음 소가 바로 검문 받을 수 있으므로
   → 소요시간 += 다음 소의 검문 시간

로 나눠서 푸니 해결했다!

 

알고리즘

• 그리디 알고리즘
• 정렬

 

코드

import sys
input = sys.stdin.readline

n = int(input())
line = []

for i in range(n):
  line.append(list(map(int, input().split())))
line.sort()

time = line[0][0] + line[0][1]
for i in range(1, n):
  if time <= line[i][0]:
    time += (line[i][0] - time) + line[i][1]
  else:
    time += line[i][1]

print(time)