백준 알고리즘 9869 - Milk Scheduling

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

9869번: Milk Scheduling

문제는 백준 알고리즘 사이트에서 확인하세요!

 

오늘 다룰 문제는 MILK SCHEDULING 문제입니다.

 

존은 소 우유를 짜는 농부인데요.

 

1. 우유를 짤 때마다 소들이 생산하는 가치(갈래온)가 다르다고 하네요.

 

시간에 맞춰 우유를 짜야합니다.

 

2. 너무 늦게 우유를 짜면 소가 거부한다고 합니다.

 

획득할 수 있는 갈래온의 양이 최대가 되게 스케쥴하는 문제입니다~

 

이번 문제는 GREEDY APPROACH를 이용한 문제입니다.

Greedy approach?   미래를 고려하지 않음! 문제를 해결하기 위한 판단 기준을 정하고 그때그때 순간마다 최선의 선택을 한다!

스케쥴링 문제는 유명한데요.

 

문제에서 필요한 부분을 캐치해보면

 

1. 우유를 짤 때마다 소들이 생산하는 가치(갈래온)가 다르다. 

2. 너무 늦게 우유를 짜면 소가 거부한다. -> Deadline

3. 획득할 수 있는 갈래온의 양이 최대가 되게 스케쥴 -> 판단의 기준

 

즉 Deadline을 지키면서 판단기준에 맞도록 스케쥴하는것이 최적화된 해답과 가깝습니다~

 

Deadline은 어떻게 지킬 수 있을까요?

 

번호	DeadLine
1	3
2	2
3	2
4	2

예를 들어보았습니다 4개의 작업이 있고, 저마다 deadline이 존재합니다.

 

어떻게 deadline을 지킬 수 있는지 알아봅시다!

 

1	2	3	4	5	6

넉넉하게 스케쥴을 작성할 공간을 만들어 줍니다~

 

번호순으로 스케쥴링을 하면

진행 번호	1	2	3	4	5	6
1			task1
2		task2	task1

앞이 비었음에도 불구하고 우선순위가 높을 수 있는 다음 작업을 위해서 Deadline끝에 배치를 합니다.

 

1번과 2번 작업은 겹치는것 없이 스케쥴 될 수 있네요

 

진행 번호	1	2	3	4	5	6
3		task2 <-task 3	task1

3번 작업은 2번과 Deadline이 겹치네요??

 

진행 번호	1	2	3	4	5	6
3	task3	task2	task1

간단히 그 앞에 배치해서 해결해줍니다.

 

진행 번호	1	2	3	4	5	6
4	task3	task2 <-task4	task1

4번도 겹치네요??

 

진행 번호	1	2	3	4	5	6
4	task3 <- task4	task2	task1

또 겹치는데 갈곳이 없습니다 흐어어..

 

이럴땐 문제에 맞게 변형해야합니다.

 

1 deadline을 넘기더라도 반드시 수행해야하는 경우)

       공간 제일 끝(6번)에 배치합니다.

 

2 deadline을 넘기면 수행할 필요가 없는 경우)

       배치된 작업들 보다 우선순위가 높은 경우) <- 판단 기준으로 우선순위를 판단합니다~

                배치된 작업 대신 현재 작업을 배치하고, 기존에 배치된 작업은 공간에서 삭제합니다.

       배치된 작업들 보다 우선순위가 낮은 경우)

                현재 작업을 건너뛰고 다음 작업을 받습니다.

 

우리는 milk scheduling 문제를 풀고있고 2번 조건에서 우유를 늦게 짜면 소가 거부한다고 했으므로 deadline을 넘기면 고려해야할 대상이 아니죠!

 

진행 번호	1	2	3	4	5	6
4	task3	task2	task1

task4는 고려하지 않습니다

 

그럼 이제 코딩~~하러 ㄱㄱ~!