[CodeJam][2017] Ratatouille - Round1A ProblemB

문제 : https://code.google.com/codejam/contest/5304486/dashboard#s=p1

---

그리디로 풀었다.

6번 case로 예를 들어보자.

3 3
70 80 90
1260 1500 700
800 1440 1600
1700 1620 900

입력으로 받은 Q배열을 재료별로 오름차순 정렬한다.

700 1260 1500
800 1440 1600
900 1620 1700

이제 각 재료를 cnt 개 사용해서 만들 수 있는 패키지를 구한다.

cnt는 1부터 시작한다.

각 재료의 그램 수는 처음 입력에서 본 것과 같이 각각 70, 80, 90 이다.

먼저 각 재료들 하나로 만들 수 있는 패키지(Q)는 없다.

하나인 경우 -> [63~77, 72~88, 81~99].

만들 수 있는 패키지가 있을 때까지 cnt를 증가시킨다. 

이 때 만들 수 있는 패키지는 Q배열의 가장 앞에 값만 비교하면 된다. (즉, 700, 800, 900 만 비교)

10개인 경우 -> [630~770, 720~880, 810~990].

cnt를 점차 증가시켰을 때 cnt가 10개인 경우 700, 800, 900이 범위 안에 있으므로 정답을 1증가시키고 다음 패키지를 탐색한다. (조건에서 하나의 패키지는 하나의 키트에만 사용할 수 있다고 했으므로)

정답이 되는 경우를 찾았을 때 cnt는 증가시키지 않는다. cnt로 만들 수 있는 또 다른 패키지가 있을수도 있기 때문이다.

만약 cnt를 사용한 재료 i의 그램의 90퍼 센트보다 i번째 재료 Q 배열의 현재 탐색하고 있는 그램수가 작다면 이는 절대 정답이 될 수 없기 때문에 다음 Q배열을 탐색한다. 

ex) 

재료 i를 cnt만큼 사용햇을 때 그램 = 100, 현재 탐색 중인 재료 i의 Q배열 요소 값 = 80 인경우, 

가능한 그램 범위는 [90 ~ 110] 이 되고 80은 이보다 작다. cnt는 커지거나 유지가 되지 작아지는 경우는 없으므로 가능한 그램 범위는 앞으로도 90이상이므로 80은 절대 정답 범위내에 속하지 않는다. -> 따라서 다음 Q배열 값을 본다.

시간복잡도는 cnt가 최대가 되는 조건을 봐야 하는데 이는, 어떠한 i번째 재료의 패키지 중 최대값(max(Q[i][0~P]))을 그램(R[i])으로 나누었을 때이다.

즉, R[i]가 1이고 max(Q[i][0~P])가 10^6인 경우 cnt가 최대가 된다.(10^6 / 1 = 10^6)

그리고 cnt 반복문 안에서 각 재료를 cnt 개 사용했을 때 정답이 될 수 있는 패키지를 구해야 하므로 N번 반복한다.

따라서 총 시간복잡도는 O(max(Q[i][0~P]) / R[i] * N) 이다.

---

소스코드 : https://gist.github.com/fpdjsns/06e0fa8c8b2ca79a9c2fd3e4cbf126a5