백준 14421 The Kingdom of JOIOI

문제 링크: https://www.acmicpc.net/problem/14421

14421번: The Kingdom of JOIOI

 

문제를 보고 18871번이 떠오르면서 이차원 dp로 무언가를 해나가고 싶었다. 하지만 안타깝게 풀이는 그렇지 않았다.

 

JOI 지역과 IOI 지역의 조건을 좀 직관적으로 해석하자면 $i$번 행에서 한 지역은 $1$열부터 $x_i$열까지 차지하고 다른 지역은 $x_i+1$열부터 $W$열까지 차지하고 $x_i$가 단조성을 띤다는 것이다.

 

일단 처음에 든 생각은 $HW$개의 숫자 중 최댓값과 최솟값이 한 지역에 같이 있으면 답이 최댓값 - 최솟값으로 정해진다는 것이다. 그래서 최댓값과 최솟값은 다른 지역에 있는 것이 좋다.

 

일반성을 잃지 않고 IOI 지역에 최댓값이 있다고 가정하자. IOI 지역이 JOI 지역보다 왼쪽에 있을 수도 있고 오른쪽에 있을 수도 있다. 그리고 $x_i$는 단조증가할 수도 있고 단조감소할 수도 있다. 땅을 적당히 회전시키면 IOI 지역이 JOI 지역보다 오른쪽에 있고 $x_i$가 단조증가하게 할 수 있다.

 

이제 일반성을 잃지 않고 IOI 지역에 최댓값이 있고, IOI 지역이 JOI 지역보다 오른쪽에 있고 $x_i$가 단조증가한다고 생각하자. IOI 지역의 최솟값을 $X$로 고정했을 때 $X$보다 작은 값을 가지는 땅들은 항상 JOI 지역에 있어야 한다. 그리고 $x_i$가 단조증가하고 JOI 지역이 IOI 지역의 왼쪽에 있어야 하기 때문에 이를 만족하기 위해 몇몇 땅들은 JOI 지역에 속해야 한다. 

 

아직 IOI 지역에 속하게 할지 JOI 지역에 속하게 할지 정하지 않은 땅들의 값은 모두 IOI 지역의 최솟값과 최댓값 사이이다. 따라서 IOI 지역에 속하게 하는 것이 이득이다.

 

따라서 JOI 지역에 속하게 되는 땅들은

1. 값이 $X$보다 작다.

2. 값이 $X$보다 작은 어떤 땅보다 왼쪽 위에 있다.

중 하나를 만족하게 된다.

 

$X$을 늘려나가면서 JOI 지역의 땅을 관리하면서 최댓값 - 최솟값을 구해보자.

$X$가 하나 증가시키면 기존의 $X$의 값을 가지던 땅은 JOI 지역에 속해야 한다. 이는 1번 조건을 맞추기 위해서이다.

JOI 지역에 땅을 하나 추가하면 2번 조건을 만족하는 땅들이 늘어서 이를 관리해야 한다. 

1번 조건에 의해 추가하는 땅이 $x$행 $y$열에 있다고 하자. $x$번 행부터 $H$번 행까지의 $x_i$ 값을 관리하자. $i$번 행을 보고 있을 때 $x_i$가 $y$보다 작으면 ($i$, $x_i+1$), ($i$, $x_i+2$), ... ($i$, $y$) 위치에 있는 땅을 JOI 지역에 추가해야 한다.

$x_i$가 $j$보다 크면 $x_i$의 단조성에 의해 $i$번 행보다 아래에 있는 행들에 대해서는 새로운 땅을 JOI 지역에 추가해주지 않아도 된다.

이를 시행하는데 필요한 시간은 JOI 지역에 추가하는 땅의 개수랑 비례해서, 총 $O(HW)$의 시간으로 해결할 수 있다.

 

정렬을 하는데 $O(HWlogHW)$, JOI 지역의 땅과 IOI 지역의 땅을 관리하는데 $O(HW)$의 시간이 들어서 총 시간복잡도 $O(HWlogHW)$에 문제를 해결할 수 있다.