주유소

백준 13305 풀이 (주유소, 그리디 알고리즘)

이거 문제를 읽고 어떤방식으로 풀어야 하는지는 바로 알아챘다. 그러나 진짜 진짜 코딩이 왤케 까다로운지 코딩때문에 시간이 오래걸렸다. 노트에는 어떤 로직으로 풀어야하는지 알겠는데 이걸 코딩으로 짜려니 이상하게 안풀렸다ㅋㅋㅋㅋ 문제는 간단하다. 주유소 가격과 거리가 존재할때 언제 주유를 하고 이동을 해야 마지막 거리까지 가장 싼 가격에 도착할 수 있는가를 묻는 문제이다. 그러면 바로 생각할 수 있는것은 i와 i+1을 비교하여 가격이 저렴한곳에서 주유를 하면된다. 그럼 규칙이 만들어진다. 1. i와 i+1의 주유값을 비교한다. i가 비싸면 i+1까지 비용을 지불하고 이동한다. 2. i가 싸다면 다음 거리까지 i에서 지불하고 이동한다. 3. 마지막 도시에 도착하는지 인덱스를 확인하여 연산을 종료한다. n = ..