04. 탐욕법 - 예제1

[1. 문제 설명]

n 개의 도시락이 있고,

i번째 도시락을 데우는데 m[i] 초, 먹는데는 e[i] 초가 걸린다.

도시락을 먹기 위해서는 도시락을 먼저 데워야 한다.

도시락을 여러번에 나누어 데울수는 없다.

모든 사람이 도시락을 다 먹을 때 까지 걸리는 최소 시간

 

 

[2. 풀이 접근]

스케줄링 문제는 보통 탐욕법으로 풀 수 있다. (모든 경우는 아님)

 

전체 시간 = n-1 개의 도시락을 데우는 시간 + 마지막 도시락을 먹는데 걸리는 시간

 

먹는데 오래 걸리는 도시락부터 데우면 된다.

 

먹는데 오래 걸리는 도시락을 먼저 데우면,

다른 도시락을 데우는 시간 동안

이 도시락을 먹을 수 있기 때문이다.

 

=== 탐욕적 선택 속성 증명

먹는데 가장 오래 걸리는 샤브샤브 도시락을 먼저 데우는 최적해가 반드시 하나 있음을 보이도록 한다.

1. 돈가스 도시락을 제일 먼저 데우는 최적해가 존재한다고 가정
2. x 번째 위치한 샤브샤브 돈가스와 위치를 바꾼 뒤, 이것 역시 최적해가 되는가를 보이도록 한다.
3. 둘의 자리를 바꿔도, x+1 번째 이후 도시락에 미치는 영향은 없다.
   => 데우는 시간 자체는 변하지 않았으므로
   => 먹는데 까지 걸리는 시간이 변하는 도시락은 0 ~ x 번째 도시락이다.
4. [0, x] 사이 도시락 중 가장 마지막에 식사가 끝나는 도시락은 항상 샤브샤브 도시락이다.
   => 샤브샤브 도시락을 먹는데 가장 오랜시간이 걸리므로, # max 로 설정
   => 순서를 아무렇게나 바꿔도, max 보다 커질 수 는 없다.
   ==> 데우는 시간은 변하지 않는다. 마지막 도시락을 먹는데 걸리는 시간이 절대적인 영향을 끼친다.
5. 따라서, 샤브샤브와 돈가스 순서를 바꾼 답이 최적해보다 더 나빠질 수 는 없다.

=== 최적 부분 구조 증명

1. 첫번째 도시락을 정하고 나면, 나머지 도시락들을 배치한다.
2. 나머지 도시락들을 다 먹기까지 걸리는 시간은 첫번째 도시락을 데우는 시간만큼 지연된다.
3. 남은 도시락들에 대해서도 가장 늦게 다 먹는 시간을 최소로 해야 전체를 최소로 할 수 있다.

 

== 기타 주의 할 점

아래 코드 참조

 

[3. 코드]