[Greedy] 주유소 - 백준 13305번

13305번: 주유소

풀이

첫번째 풀이 (잘못된 풀이)

• 바로 옆에 있는 주유소의 가격이 현재 주유소 가격보다 크거나 같을 경우 다음 주유소도 이전 주유소 가격으로 계산한다.
  • 두 개씩 묶어서 합침

    4
    2 3 1
    5 2 4 1
  

  5(oil) * 2(road) = 10

  5 > 2 ⇒ 기름을 이어서 쓰지 않는다.

  2(oil) * 3(road) = 6

  2 ≤ 4 ⇒ 기름을 이어서 쓴다.

  2(oil) * 1(road) = 1

⇒ 첫번째 주유소에서 끝까지 다 가야한다. = 6

4
1 2 3
1 2 3 4

두개씩 묶으면

1(oil) * 1(road) = 1

1 ≤ 2 ⇒ 기름을 이어서 쓴다.

1(oil) * 2(road) = 2

2 ≤ 3 ⇒ 기름을 이어서 쓴다.

2(oil) * 3(road) = 6

정석 풀이 (Greedy 알고리즘)

주유소 하나씩 지나갈 때마다 가장 적은 기름 값으로 주유한다.

4
1 2 3
1 2 3 4

주유소 1번에서는 1원으로 1km으로 달려 총 1원을 사용한다.

다음 2번 주유소에서는 2원으로 1원이 더 싸다 1원으로 2km으로 달려 총 2원 사용한다.

마찬가지로 3번 주유소에서는 3원으로 1원 짜리 주유소에서 받아온 기름을 사용한다. 3km으로 달려 총 3원

동일하게 4원사용해서 총 10원 사용한다.

4
2 3 1
5 2 4 1

주유소 1번에서는 5원으로 2km를 달려 총 10원 사용 (minimum = 5)

주유소 2번에서 2원으로 (minimum(5) > 2) 2원 주유소를 이용 3km를 달려 6원 사용 (minimum = 2)

주유소 3번에서 (minimym(2) < 4) 2원 주유소 기름을 사용 1km를 달려 2원 사용 (minimum = 2)

총 18원 사용

코드

https://github.com/KimGyeongLock/CodingTest/blob/main/13305.cpp