https://programmers.co.kr/learn/courses/30/lessons/42884

  • flow
    그리디 알고리즘? routes 리스트를 정렬한 후, 순서대로 겹치는 부분을 확인해 나아가면 될 듯함
    정렬 했을 때, 순서대로 A와 B가 겹치는 부분 존재하고, B와 C가 겹치는 부분 존재하면서 A와 C가 겹치지 않을 때, 그냥 A와 B가 겹치는 부분 아무곳이나 하나 카메라를 설치해도 최적화 해가 됨. C는 A와 B를 무시하고 그 다음 D, E 등등과 비교해 나아가면 됨.
    A와 B와 C가 모두 겹치는 부분이 있으면 그 부분을 D와 비교, 이런 식으로 정렬된 인덱스 순서대로 나아가면 부분해가 전체의 최적화 해가 되는 그리디 알고리즘 적용 가능한 문제
    시간 복잡도는 O(N) 이라 좋음

  • result
    https://github.com/songjy6565/alg-py/blob/master/programmers/level3/A7.py