« 2022/11 »
관리 메뉴
목록분류 전체보기 (260)The Way*.. .*. *.. 와 같은 식으로 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 ..
|