그리디(greedy) - 주유소

1. 문제 해결의 아이디어

  ① 최소 비용 계산 -> 가장 싼 값의 기름을 최대한 많이 사야함

  ② 계산 방식
    - 문제 상황 그대로 접근 : 주어진 기름값 목록에서 최솟값을 찾고, 그 도시에서 목적지까지 가는 데 필요한 기름을
                                          그 가격으로 몽땅 구입하는 식으로 계산.
    - 그리디 알고리즘 : 도시를 하나씩 지나가며 그 도시의 가격과 이전 도시의 가격을 비교해서 당장 싼 가격으로 다음
                                  도시로 가는데 필요한 기름만 사는 식으로 계산.

 

2. 소스 코드

  - 문제 상황 그대로 접근

 

  - 그리디 알고리즘

 

3. 평가

  - 처음에 문제 상황 그대로 구현을 했더니 시간 초과가 났다. 최대로 주어질 수 있는 도시 개수가 10억 개라서
    최솟값 계산에 인덱스 계산 등을 반복하니 시간복잡도가 치솟은 듯.

  - 뒤늦게 반복문으로 그냥 도시 하나씩 돌면서 계산하면 된다는 걸 깨닫고 다시 짜서 통과하긴 했는데
    아직도 그리디에 대한 이해를 못하고 있는 것 같다. 엿댔다.