[코드트리]함께 가는 열차

풀 땐 몰랐는데, 풀고나니 분류가 그리디였다. 그리디 문제는 풀고나서 분류를 보고 '아~ 그리디였구나' 하고 알게 되는 것 같다. 그리고 못 푼 경우에도 '아.. 그리디였구나ㅠㅠ' 이러고... dfs, bfs, dp문제는 문제를 보면 바로 이렇게 풀어야겠구나~! 하고 알겠는데 그리디는 항상 모르겠다...ㅠㅠ

 

https://www.codetree.ai/training-field/search/problems/a-train-that-goes-together?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

일단 이 문제는 무한히 긴 선로를 같은 방향으로 열차가 무한히 이동하면 어떻게 되는지 묻는 문제다. 

 

앞에서 달리는 열차가 뒤에서 달리는 열차보다 더 빠르다면 (선로가 무한히 길기 때문에)시간이 무한히 지나도 만날 수 없다. 

만약, 앞에서 달리는 열차의 속도가 뒤에 있는 열차보다 느리다면 뒤에 있는 열차는 언젠가 앞 열차와 합쳐지고 느린 앞 열차의 속도로 바뀌게 된다.

 

그러므로, 맨 앞에서 달리는 열차의 속도를 v라고 할 때, 뒤에 따라오는 열차의 속도가 v보다 작으면 결과적으로 앞 열차와 만나지 못하는 새로운 열차 덩어리가 생긴다.

 

n = int(input())

trains = []
minV = 1000000000
cnt = 0
for i in range(n):
    p,v = map(int,input().split())
    trains.append((p,v))


trains.reverse()

for (p,v) in trains:
    if minV >= v:
        minV = v 
        cnt += 1
        
print(cnt)

 

그리디 문제를 직관적인 감으로 풀고 있었는데, 그러다보니 조금만 문제가 어려워지면 풀지 못할때가 종종있다.

그리디 알고리즘의 수학 증명을 잠깐 찾아봤는데 생각보다 복잡했다...음...그리디는 조만간 좀 더 공부해서 포스팅 해야겠다.