Greedy 예제(7) Gas Station

예제) 원을 따라 주유소가 다섯 곳이 있다. 주유소마다 주유할 수 있는 기름양은 다르다. 자동차는 한 곳의 주유소를 선택하여 주유를 한 뒤 이동한다. 주유소를 거칠 때 마다 주유소에서 제공하는 기름양만큼 주유가 가능할 때, 자동차가 원 한 바퀴를 돌 수 있으려면 어떤 주유소에서 출발해야 하는가?

 

 

 

 

주유소A에서 시작해보자. 

A	B	C	D	E
5	4	3	도착X

( 자동차가 각 주유소를 출발할 때 기름의 양)

 

주유소B에서 시작해보자.

B	C	D	E	A
1	도착X

( 자동차가 각 주유소를 출발할 때 기름의 양 )

 

이렇게 하나씩 접근하면 오래 걸린다. 

Greedy한 접근법을 사용하면 쉽게 처리할 수 있다. ( 현재를 기준으로 최적의 선택을 하는 방법 )

 

 

주유소A 부터 다시 해보자.

 

현재 기준 : 주유소 A 

A	B	C	D	E
5	3	1	도착X

( 자동차가 각 주유소를 출발할 때 기름의 양)

 

다음 : 주유소B

 

주유소B는 출발할 때 기름양이 1이다. 

주유소A에서 출발하여 주유소B를 들리고 출발할 때 기름양이 4이다. 

고로, 주유소B 경우는 탐색을 안 해봐도 실패가 확실하다.

 

 

다음 : 주유소C

 

주유소C는 출발할 때 기름양이 2이다

주유소A에서 출발하여 주유소C를 들리고 출발할 때 기름양이 3이다.

고로, 주유소C는 탐색을 안 해봐도 실패가 확실하다.

 

 

현재 기준 : 주유소D

 

자동차는 주유소D를 들린적이 없다. 

그러므로 현재기준은 주유소D가 된다.

D	E	A	B	C
3	도착X

( 자동차가 각 주유소를 출발할 때 기름의 양 )

 

현재 기준 : 주유소E

 

자동차는 주유소E를 들린적이 없다.

그러므로 현재기준은 주유소E가 된다.

E	A	B	C	D
4	8	7	6	5

( 자동차가 각 주유소를 출발할 때 기름의 양 )

 

성공이다.

 

Greedy한 접근법을 사용하여 주유소B와 주유소C를 탐색하는 비용을 줄일 수 있었다.

 

 

---

 

참고영상