백준 - RPG(1315)

문제

 

문제에서 다음의 조건중 하나가 성립하면 i번 퀘스트를 깰수 있었다.

1. STR $\leqslant$ STR[i]

2. INT $\leqslant$ INT [i]

 

게임 중간의 어떤 상태에 대해 생각해보자.조건 1에 의해 가장 마지막으로 깬 게임을 i번 게임, 조건 2에 의해 가장 마지막으로 깬 게임을 j번 게임이라고 하면, $\text{STR[k]} \leqslant \text{STR}[i]$ 인 k번 게임들과 $\text{ INT [k]} \leqslant \text{INT}[i]$ 인 k번 게임들은 모두 깨져 있거나 깰 수 있다.

 

STR에 의해 정렬된 퀘스트 배열 a와 INT에 의해 정렬된 퀘스트 배열 b가 있다고 하자. 우리가 방금 한 관찰에 따르면 게임을 플레이 하는 도중 퀘스트들의 상태는 $(i, j)$를 통해 $a_1 \sim a_i$와 $b_1 \sim b_j$번 퀘스트 들이 깨져 있는 것으로 나타낼 수 있다. 그러면 dp[i][j]는 상태 $(i,j)$가 도달 가능하면 true, 불가능하면 false로 정의할 수 있다.

 

그러면 문제의 답은 dp[i][j]가 true인 모든 $(i,j)$에 대해 퀘스트들의 개수의 최댓값으로 구할 수 있다.

 

점화식 또한 어렵지 않게 구할 수 있다.

$$
\text{dp}[i][j] = (\text{dp}[i][j] \text{  and  } f(i-1,j)_1 \geqslant \text{STR}[a_i]) \text{  or  } (\text{dp}[i][j] \text{  and  } f(i,j-1)_2 \geqslant \text{INT}[b_j])
$$

이때 $f(x_1,x_2)=(y_1,y_2)$이고, $y_1$과 $y_2$는 각각 게임 도중 상태 $(x_1,x_2)$에 도달했다고 가정할때 STR, INT의 최댓값이다. $f(\cdot)$은 구하지 어렵지는 않으나, 구현할때 은근 햇갈리는 부분이 있다.

 

$f(\cdot)$에 메모이제이션을 사용할 경우 dp를 계산할때 $O(N^2)$, 답을 구할때 $O(N^3)$이 결려서 최종적인 시간복잡도는 $O(N^3)$가 된다.