[ICPC 본선 대비 뇌셋] Day 3

숙제와 시험이 너무 많고 보물찾기 문제가 너무 어려워서 못쓸뻔했지만 정원은 나름 쉬워서 먼저 풀이를 적는다.

백준 5484번 정원 www.acmicpc.net/problem/5484

5484번: 정원

별로 생각 안하고 짜도 되지만 구현이 좀 더럽다. 또, 풀이에서는 1베(one based)를 쓰는 것이 이롭다는것을 느꼈다.

 

전처리: 모든 가능한 sub 가로줄과 sub 세로줄의 장미수를 구한다. --> 250^3 = 1e7

문제를 보는 순간 (i, j)를 왼쪽 아래 꼭지점으로 가지고 정확히 k개 장미를 가지는 직사각형의 최소 둘레를 구하고 싶다.

(i, j)칸을 왼쪽 아래 꼭지점으로 가지는 직사각형을 생각하자. 이제 오른쪽 위 꼭지점 A = (x, y)를 (i, n)를 출발점으로 하여 (n, j)로 이동할 것이다.

원하는 값을 구하기 위해서 A점 좌표는 y--또는 x++만 해도 무방하다. 각 과정에서 전처리를 이용하면 내부의 장미 수를 O(1)만에 구할 수 있다.

최소 장미수를 INF로 설정

내부 장미수 > k   : y--

내부 장미수 == k : y-- 둘레 최소를 갱신한다.

내부 장미수 < k   : y++, x++

이동을 2 * 250번만에 끝낼 수 있으므로 500번만에 최소둘레를 구할 수 있다.

모든 칸에 대해서 위 과정을 수행하면 2 * 250^3 = 2e7.

한편, 각 칸을 오른쪽 위 꼭지점으로 가지는 최소 장미수도 같은 방법으로 쉽게 구할 수 있으므로 이것도 구해놓자.

이제 겹치지 않게 두개를 고르는 과정만 남는다.

 

[관찰 1]

겹치지 않는 두 직사각형에 대해서,

하나의 직사각형 꼭지점의 x좌표가 다른 직사각형의 꼭지점의 x좌표보다 작거나

하나의 직사각형 꼭지점의 y좌표가 다른 직사각형의 꼭지점의 y좌표보다 작다.

 

관찰 1에 의해 다음과 같이 기준(i, j)을 잡는 것이 정당화되고, 두 둘레 합의 최소를 구할 수 있다.

점 (i, j)를 오른쪽 위 꼭지점으로 가지는 직사각형의 최소 둘레 a를 알고 있으므로,

k>=i 또는 l>j를 만족하는 (k, l)에 대해서 (k, l)을 왼쪽 아래 꼭지점으로 가지는 직사각형의 최소 둘레의 최소값 b을(표현 망했다.) 구하면 a + b는 답의 후보가 된다.

한편, 모든 i에 대해 (k(>=i), l)를 왼쪽 아래 꼭지점으로 가지는 직사각형의 최소 둘레의 최소값을 미리 저장하는 것은 250^2.

이것을 모든 j에 대해 같은 전처리를 해준다.

모든 (i,  j)쌍에 대해서 (a + b)값의 최솟값을 구하면 끝.

INF보다 크거나 같은값이 나오면 NO를 출력한다.

 

문제가 좀 많이 더럽긴 하다. 점 범위를 늘려도 풀 수 있는 문제일 것 같은데 거기까지 생각하지는 않았다. Day 1에서 생각과정, 풀이, 코딩순으로 작성하기로 했는데, 생각 == 풀이이거나 떠올리기 쉬우면 생각과정은 적지 않는게 가독성에 나을것 같다. 내일은 보물찾기를 풀 수 있었으면 좋겠다.