6.free

[문제]

고급 주택의 청소만을 전문으로 하는 1인 기업 프리랜서 HCC(House Cleaning Company)가 있다. 이 사람은 소비자들의 요청을 미리 받아서 종합하여 그중에서 가장 이익이 많도록 작업을 선택 조정한다. 작업 단위는 일(daily) 단위이며 365*3(년)까지의 일정을 그전에 모두 확정한다. 사용자들은 자신의 집을 청소하기 원하는 기간(일단위)와 그때 지불할 비용을 Mr.X의 블로그에 올린다. 청소를 신청한 고객을 라고 할 때 이를 나타내는 신청 정보는 $(b_i, e_i, c_i)$로서 각각은 시작일과 종료일, 그리고 견적 비용(cost, 만원)을 나타낸다. 이 값은 조건, $1 \leq b_i \leq e_i \leq 365 * 3$을 항상 만족한다. 최소한 기간은 하루(a day)이다.

 

HCC는 1인 기업이므로 특정 시간에 두 군데 이상의 작업을 동시에 하지 않는다. 그리고 한번 시작한 작업은 해당 집의 작업이 완전히 끝날 때까지 중지하지 않는다. 그런데 한 집을 마치고 다른 집으로 작업 장소를 바꿀 때마다 청소, 정리정돈, 재료 보충들의 준비작업에 비용(손실)이 발생한다. 이 문제에서는 주택을 바꿀 때마다 동일하게 10만원의 비용 손실을 본다고 가정한다. 따라서 같은 이득이라면 가능한 작업 장소의 개수를 줄이는 것이 더 이득이 된다.

 

HCC는 조건을 만족하는 선에서 최대 이익을 확보하기 위하여 작업 일정을 꼼꼼하게 계산해야 한다. 단, 작업 장소를 옮길 때마다 감수해야 하는 이동, 준비작업으로 소비되는 추가 비용 10만원까지도 반드시 고려해야 한다.

 

만일 같은 액수의 이익을 보장하는 일정이 하나 이상 존재하면 그 중에서 작업하는 일수가 제일 적은 것을 선택해야 한다. 예를 들어 두 일정 A, B 모두가 200만원을 보장하는데, A는 8일간, B는 6일간 일을 하는 것이라면 당연히 B를 더 선호한다.

 

출력으로는 최대로 얻을 수 있는 이득 $P$와 그것을 위한 최소 작업일 수(minimum working days for the max profit) $D$, 이 두 개의 정수 $P, D$를 출력해야 한다. 단 이득계산에는 이동 비용손실을 고려한 최종 금액이 되어야 한다.

 

 

일자	D1	D2	D3	D4	D5	D6	D7	D8	D9
요청된 작업 일정	U1 ( 1, 4, 45 )						U2 ( 7, 9, 35 )
			U3 ( 3, 7, 75 )
		U5 ( 2, 5, 67)
	U7 (1, 2, 24 )			U6 ( 4, 6, 32 )				U4 (8, 9, 15)

[입출력]

입력화일 free.inp의 첫 줄에는 신청한 작업의 수 $N$이 들어온다. ($3 \leq N \leq 100) 이어지는 $N$개의 줄에는 각 신청의 정보 $(b_i, e_i, c_i)$을 나타내는 3개의 정수가 한 줄에 나타난다. 출력은 2개의 정수 $P, D$로 구성된다. $P$는 최대의 예상 이익(만원), $Q$는 그 이익을 달성하기 위해서 일을 해야 하는 최소의 날짜 수이다. 한 집의 청소를 마치고 새로운 의뢰인의 집으로 이동할 때마다 10만원의 비용이 들어가므로 이 값은 받은 금액에서 공제해야만 한다. 이렇게 이동 비용까지 모두 공제하고 남은 비용이 실제 얻을 수 있는 이익이고 이것을 최대로 확보해야 한다.

 

 

free.inp	free.out
7 // 7개의 요청 1 4 45 7 9 35 3 7 75 8 9 15 2 5 67 4 6 32 1 2 24	94 9
4 // 4개의 요청 1 4 45 7 9 35 3 7 75 8 9 15	80 7

 

[풀이] O($365*3 * N$)

간단한 knapsack DP다. 솔직히 너무 간단해서 풀이를 하는 것 조차 애매하다.

어떤 작업 $n$의 선택(할지 않할지)을 결정하는데에 필요한 정보는 단 하나다. 현재의 날짜. 

그리고, 어떤 날 $i$에 할 수 있는 작업의 목록은 작업 시작시간이 $i$보다 크거나 같은 날들이다.

 

따라서, dp table $dp[i]$를 다음과 같이 정의할 수 있다.

$dp[now] = max(dp[arr[i].end + 1] + arr[i].cost - 10, (단, arr[i].start >= dx1)$

이렇게 dp table을 정의하면 $dp[0] + 10$ 이 정답이다. (처음 작업 선택 시 10만원을 안 빼줘도 되는데 빼줬으므로)

 

최소 일하는 시간을 구하는 것도 간단하다.

dp table을 채워나가는 과정에서,  만약 dp테이블이 max값으로 업데이트 되면 minWorkDay 배열도 update시켜주고, max값이 dp테이블과 같으면 minWorkDay배열의 min값을 잡아주면 된다.

 

두번째 dp문제치고 너무 간단해서(아마 solution추적과정을 위해 출제한 듯) 놀랬다.

 

[코드]

 

 

================ 21.03.24 추가

 

[풀이] O($N\log_2N$)

냅색 dp인데 for문이 dp테이블 탐색에 for문이 들어가는게 심히 걸리적거렸다.

그래서 전통 냅색dp처럼 $i$번째를 선택하거나 or 안 하거나 로 나누어서 2가지로 생각해주었다.

이때 dp table $dp[i]$는 다음과 같이 정의할 수 있다.

$dp[i-th-item] = max(dp[(i+1)-th-item], dp[j-th-item])$$,   $$j는 i.end + 1보다 크고, start가 가장 작은 녀석$

$j$를 찾을 때는 입력을 start로 정렬한 뒤, $i.end +1$을 기준으로 lower_bound를 걸어버리면 된다.

 

 

또 다른풀이로는 입력으로 들어오는 time들 자체를 압축시켜서(입력받고, 정렬 후 index로 시간관리) 하면 처음 풀이보다 더 빨라지고, 시간 크기에 영향을 받지 않는다.

 

[코드]