BOJ 27548 - Zrinka

BOJ 27548 - Zrinka

에디토리얼이 깔끔해서 이걸로 설명을 대체한다.

The first two subtask can be solved using greedy approach.

For full points we will use dynammic programing.

Let dp(i,j,flag) represent the solution if we only consider the first i positions of the first array, the first j positions of the second array, and if the largest number is in the first array, then flag = 0, otherwise flag = 1 (and the largest number is in the second array).

For the transition we need only to consider 4 states: ((i − 1, j, 0), (i − 1, j, 1), (i, j − 1, 0), and (i, j − 1, 1)), so the final complexity is O(nm).

For details check the official code.