(JAVA) 백준 13305번 : 주유소

https://www.acmicpc.net/problem/13305

13305번: 주유소

 

안녕하세요.

 

그리디 알고리즘 문제로, 난이도는 중 이다.

 

 

알아야 할 부분을 정리하자면,

 

  -  N개의 도시, N-1개의 도로

  -  1km -> 1L

  -  원 안의 숫자 : 리터당 가격. 즉, 1km 당 가격

  -  왼쪽부터 순차적으로 이동해야 함

 

 

정도가 된다.

 

 

문제 해결 방법은 더욱 쉽다.

 

여기서 구하고자 하는 것은 시작 도시부터 도착 도시까지 이동하는데 드는 최소 비용 이다.

 

 

그럼 최소 비용으로 가기 위해서는??

 

리터당 가격이 가장 낮은 곳에서 기름을 최대한 많이 넣어야 한다.

 

 

바꿔말하면

 

현재 도시의 리터당 가격이 다음 도시의 리터당 가격보다 낮으면 다음 도시에서 다다음 도시까지의 이동거리만큼 주유한다.

 

가 된다.

*** 처음 시작 도시에서는 무조건 기름을 넣어야 다음 도시로 이동할 수 있다. 그렇기 때문에, 현재 도시에서 다음 도시까지 이동하는 거리만큼의 주유는 이미 한 상태라고 가정하고 위 알고리즘을 적용한다.

 

 

복잡하게 생각할 필요 없이 도시의 리터당 가격만 놓고 비교하여 

 

  -  현재 있는 도시의 가격이 다음 도시보다 낮다 (현재 있는 도시 가격 < 다음 도시 가격)

      -> 다음 도시에서 다다음 도시까지 이동거리만큼 현재 있는 도시에서 주유하고, 다다음 도시의 가격과 현재 있는 도시의 가격을 다시 비교한다.

  -  현재 있는 도시의 가격이 다음 도시보다 같거나 높다 (현재 있는 도시 가격 >= 다음 도시 가격)

      -> 다음 도시에서 다다음 도시까지 이동거리만큼 다음 도시에서 주유하고, 다다음 도시의 가격과 다음 도시의 가격을 비교한다.

 

 

매커니즘

---

 

백준 문제의 예제이다. 앞에서부터 차례대로 a=5, b=2, c=4, d=1 이라고 하자.

 

 

1)  a -> b 이동을 위해서는 a도시에서 반드시 주유해야 하므로, 10원을 소모하였다. (+10)

 

2)  b -> c 이동을 위해 주유를 해야 한다.

 

3)  a도시의 가격과 b도시의 가격을 비교한다. (a > b)

 

4)  b도시의 가격이 저렴하므로, b도시에서 b - c 거리만큼 주유한다. (+6)

 

5)  c -> d 이동을 위해 주유를 해야 한다.

 

6)  b도시에서 주유했으므로, b도시의 가격과 c도시의 가격을 비교한다. (b < c)

 

7)  b도시의 가격이 저렴하므로, b도시에서 c - d 거리만큼 주유한다. (+2)

 

8)  도착 결과, 18원을 소비하였다. (최소 비용)

 

 

 

이러한 매커니즘으로 코드 작성을 하면 된다.

 

자세한 사항은 하단 소스코드를 참고하면 된다

 

 

이상입니다.

 

감사합니다!

 

 

 

소스코드

---