[Hard] KingdomXEmergencyStaircase

어떤 영역에 계단을 하나 설치해서 그 영역이 둘로 나뉘어졌다면 그 둘은 독립적으로 뻗어나간다 이를 통해 dp를 생각할 수 있다 D( 현재 영역 ) = min( D( 나눠진 영역 1 ) + D( 나눠진 영역 2 ) + (나누는 비용) ) 영역을 어떻게 상태로 나타낼지가 관건이다 에디토리얼에선 조금 복잡한 방법을 제시했는데 연습방에서 소스를 죽 훑어보니 stjepan 이라는 사람의 아이디어가 아주 간단하면서도 참신해서 그것을 설명하겠다 사다리를 설치하면서 생기는 영역들은 모두 직사각형을 45도 돌린 뒤 양쪽 귀퉁이를 적당히 자른 (혹은 자르지 않은) 모양이다 이 영역을 다음과 같이 표현할 수 있다 왼쪽 빌딩 벽에서 점 l0, l1 을 잡고 오른쪽 빌딩 벽에서 점 r0, r1 을 잡아서 l0에서 오른쪽 아래로 반직선, r0에서 왼쪽 아래로 반직선을 그어 만나는 교점 l1에서 오른쪽 위로 반직선, r1에서 왼쪽 위로 반직선을 그어 만나는 교점 이 두 점과 모두 접하는 영역이 바로 우리가 관심있는 영역이 된다 따라서 dp 상태를 D(l0, l1, r0, r1) 으로 나타낼 수 있고 l0에 대해 가능한 r0의 범위는 [l0 - w, l0 + w], l1에 대해 가능한 r1의 범위는 [l1 - w, l1 + w] 이므로 상태의 수는 대략 120 * 20 * 120 * 20 정도로 시간내에 계산할만한 양이다 현재 상태에서 직선을 그을 수 있는 경우를 잘 고려하면 점화식도 쉽게 생각할 수 있다 예를 들어 오른쪽 위로 긋는 경우에 대한 점화식은 D(l0, l1, r0, r1) = min( D(l0, i, r0, min(i + w, r1)) + D(max(i, l0), l1, i + w, r1) + cost[(w + min(i + w, r1) - max(i, l0)) / 2] ) ( r0 - w < i < l1 ) 이다 왼쪽 위로 긋는 경우는 그냥 전체 상태를 좌우반전 시킨 후 오른쪽 위로 긋는 것으로 생각할 수 있다. 문제의 조건에 의해 만들 수 없는 상태도 있다. 예를 들면 y - x < 0 && y + x < w 인 영역엔 사다리를 설치할 수 없고 맨 위에 가상으로 만든 경계에는 사다리를 연결하면 안된다 이런 경우들을 잘 체크해야한다