백준 18778번: Equilateral Triangles

*..
.*.
*..

와 같은 식으로 n * n 크기의 board가 주어질 때, manhattan distance를 기준으로 정삼각형을 이루는 세 쌍의 *의 수를 구하는 문제이다.

모든 쌍을 다 해보려면 시간 복잡도는 $O(n^6)$이고, 점을 두 개만 고르면 나머지 한 점의 가능한 위치는 정해지므로 이 방법을 사용한다 해도 시간 복잡도는 $O(n^4)$이다. n = 300이므로, 조금 더 나은 방법을 찾을 필요가 있다.

 

먼저 적절한 관찰을 통해 정삼각형이 가지는 특징을 알아낼 필요가 있다.

한 변의 길이가 d인 정삼각형은 적절한 90도 단위의 회전을 통해, 좌표가

$(p, q), (p + x, q + (d - x)), (p + y, q + (d - y))$

$(0 \le x \le d, 0 \le y \le d)$가 되도록 만들 수 있다.

 

엄밀하게 써 보려니 좀 복잡한데, 결국은 가장 왼쪽 아래에 위치하는 점(즉, 다른 두 점의 x, y좌표가 모두 해당 점보다 큰 점)이 존재한다는 것이다.

증명은 대충만 설명하자면, 위 예시가 불가능하려면 x좌표가 가장 작은 점 기준으로 다른 두 점의 y좌표가 하나는 위, 하나는 아래가 되어야 하고, 이러면 두 가지 케이스가 생기는데 둘 다 잘 돌려보면 된다.

 

결과적으로 위와 같이 A로 표시될 수 있는 점이 존재하며, 이 때 한 변의 길이가 d이므로 우리의 가정 하에서 나머지 두 점은 회색으로 표시된 선 위에 존재한다. 즉, 나머지 두 점은 같은 대각선 하에 위치하게 된다.

 

뭔가 말이 길었는데, 도출되는 결론은 간단하다.

manhattan distance 상의 정삼각형은 최소 두 점은 대각선상에 위치한다.

 

주어진 board에서의 총 2 * n개의 대각선(정방향, 역방향)이 있고, 해당 대각선 상에서 두 점의 pair를 골라보면 경우는 총 $O(n^3)$으로 줄어들게 된다.

그렇다면 이제는 반대로 대각선에 위치한 두 점의 pair를 골랐을 때, 나머지 한 점이 어디에 위치할지가 중요하다.

두 점이 대각선으로 놓였을 때, 나머지 한 점으로 가능한 위치는 위 그림 기준 파란색으로 정해진다.

해당 위치에 점이 총 몇 개 있는지를 세 주면 되므로 대각선 단위 누적합을 미리 만들어놓으면 $O(1)$에 계산 가능하다.

따라서 전체 시간 복잡도 $O(n^3)$에 답을 구할 수 있다.

 

주의할 점은 양 끝(삼각형으로 표시)에 놓인 점은 대각선변을 2개 생성하므로 중복으로 카운팅된다. 이를 잘 제외하고 세자.

 

18778.cpp