boj 11001: 김치

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

11001번: 김치

(숙성 시간) * (김치를 꺼낼 때의 온도) + (김치를 넣은 날 가치) 의 최대값을 출력해주는 문제이다.

---

Divide And Conquer 최적화 기법을 사용하여 해결할 수 있다.

 

Divide And Conquer 최적화 기법을 적용하기 전, 전제 하나를 증명하고 시작하자.

 

[전제 증명]

 

*전제1*

i0 < i1, j0 < j1일 때,

i0번째 날에 담근 김치를 j0번째 날에 꺼내는 것보다 j1번째 날에 꺼내는 것이 더 맛이 좋다면,

i1번째 날에 담근 김치도 j0번째 날에 꺼내는 것보다 j1번째 날에 꺼내는 것이 좋다.

 

그림을 통해 살펴보자.

 

그림에서, i0번째 날에 담근 김치를 j0번째 날에 김치를 꺼냈을 때 가치는 S1 + S0 이고,

j1번째 날에 김치를 꺼냈을 때 가치는

S1 + S2 이다.

j0번째날에 꺼낸 김치보다 j1번째 날에 꺼낸 김치가 더 맛이 좋다면, S0 < S2 이다.

 

 

이번엔 i1번째날을 그림으로 살펴보자.

i0 < i1 이므로, S'0 < S0 이다.

그런데, S0 < S2 이므로, S'0 <S2 이 성립한다.

 S'0 <S2 이므로, j0번째 날에 꺼낸 김치보다 j1번째 날에 꺼낸 김치가 맛이 좋다.

 

이로써 i0 < i1, j0 < j1일 때, i0번째 날에 담근 김치를 j0번째 날에 꺼내는 것보다 j1번째 날에 꺼내는 것이 더 맛이 좋다면, i1번째 날에 담근 김치도 j0번째 날에 꺼내는 것보다 j1번째 날에 꺼내는 것이 좋다는 것을 증명하였고,

 

*전제2*

i0 < i1, j0 < j1일 때,

i1번째 날에 담근 김치를 j1번째 날에 꺼내는 것보다 j0번째 날에 꺼내는 것이 더 맛이 좋다면,

i0번째 날에 담근 김치도 j1번째 날에 꺼내는 것보다 j0번째 날에 꺼내는 것이 좋다.

 

*전제2*도 위의 그림으로 설명한 것과 동일한 방법으로 증명 가능하다.

 

 

[DnC Optimiztion]

 

i0 < i1 < i2일 때,

i1번째 날에 담근 김치를 k번째 날에 꺼내는 것이 가장 좋다면, i0번째 날에 담근 김치는 'k이하'번째 날에 꺼내는 것이 가장 좋고, i2번째 날에 담근 김치는 'k이상' 번째 날에 꺼내는 것이 가장 좋다.

 

 

위의 그림처럼, l0와 r0의 중간값을 m0라고 할 때, m0번째 날에 담근 김치를 꺼내는 날짜를 정한다.

m0번째 날에 담근 김치를 꺼내기 가장 좋은 날짜를 m1이라고 할때,

l0 ~ m0-1번째 날 담근 김치는 l1~m1날 사이에 꺼내는 것이 좋고, m0+1~r0번째 날 담근 김치는 m1~r2번째 날 사이에 꺼내는 것이 좋다.

이제, l0~m0-1번째날과 m0+1~r0번째날 각각에 대해 동일한 문제를 재귀적으로 풀어나가면 된다.