[BOJ] 1028번: 다이아몬드 광산

https://www.acmicpc.net/problem/1028

R과 C가 엄청 크지는 않아서 그냥 크기를 고정하고, 각 중심점에 대해 다이아몬드가 이루어지는 확인하는 방법으로도 간당간당하게 시간 내로 풀어낼 수 있는 것으로 알지만 DP를 활용하면 조금 더 빠르게 풀 수 있습니다.

D1[770][770]; // D1[r][c] : (r, c)를 시작점으로 했을 때 북동쪽 방향으로 1이 최대 몇개까지 이어지는가

D2[770][770]; // 남동

D3[770][770]; // 남서

D4[770][770]; // 북서

로 둡니다. D1, D2, D3, D4를 O(RC)에 채울 수 있음은 자명합니다.

이제 각 격자점들을 다이아몬드의 왼쪽 꼭짓점으로 두는 상황을 생각해봅시다. 그러면 자연스럽게 min(D1[r][c], D2[r][c])가 그 왼쪽 꼭짓점으로부터 최대한 뻗어나갈 수 있는 변의 길이일 것입니다. sz = 1~min(D1[r][c], D2[r][c])에 대해, (r, c+2*sz-2)가 오른쪽 꼭짓점이 됩니다. 그러므로 min(D3[r][c+2*sz-2], D4[r][c+2*sz-2]) >= sz이면 크기가 sz인 다이아몬드를 찾은 것입니다. 이 것을 모든 다이아몬드에 대해 수행하면 됩니다.

최악의 경우 O(RC*min(R,C))이긴 하지만 탐색의 순서를 조정하면 중간에 탈출해서 답을 출력하기 때문에 최악의 경우를 볼 일이 거의 없습니다.

https://github.com/blisstoner/BOJ/blob/master/1028.cpp