BOJ - 정사각형의 개수(1540)

링크 : https://www.acmicpc.net/problem/1540

---

문제 설명

세준이는 2차원 평면에 N개의 점을 찍었다. 그리고 나서 정사각형의 개수를 세려고 한다.

정사각형의 개수란, 세준이가 찍은 서로 다른 N개의 점을 꼭짓점으로 하며, 모든 변은 축에 평행한 서로 다른 정사각형을 모두 센 것이다.

세준이는 정사각형의 개수를 최대로 하려고 한다.

N이 주어졌을 때, 정사각형의 개수의 최댓값을 구하는 프로그램을 작성하시오.

제한조건

첫째 줄에 N이 주어진다. 이 값은 0보다 크거나 같고, 1000000보다 작거나 같은 값이다.

---

코드

#include <iostream>
#include <math.h>

using namespace std;

int main(){
    // ios::sync_with_stdio(false);
    // cin.tie(NULL);
    int ans = 0;
    int N;
    cin >> N;
    
    int x = int(sqrt(N));
    int interval = N - (x*x);

    for (int i = 1; i < x; i++){
        ans += i*i;
    }
    int stack = 0;
    for (interval; interval > 0; interval--){
        ans += stack;
        stack = (stack+1)%x;
    }
    cout << ans;
    return 0;
}

---

아이디어

점화식을 구하는 문제인 것 같길래 규칙을 찾아보며 45도 돌아간 정사각형은 대상이 아니고, 정사각형의 개수가 가장 많을 두는 방식을 깨닫는다.

1. 먼저 N이 x^2이라면 정사각형은 ∑ (x-i)^2 개의 정사각형을 가지니 모두 더하면 된다. 그래서 N에 제곱근을 활용해 N 이하에 x^2을 찾아서 모두 더한다.

2. N과 x^2에 점의 개수(interval)를 확인한 후 점을 하나 추가할 때마다 생기는 정사각형을 더한다. 순서는 파란색 숫자로 추가하면 하나를 추가할 때마다 0, 1, 2, ... n-1개의 상자가 추가되고 우측면을 모두 했다면 아랫면으로 다시 한번 똑같은 정사각형 추가 개수가 진행된다.  그래서 개수를 하나씩 세면서 새로 생긴 상자 개수를 추가해주고, 한쪽면이 모두 처리됐다면 다른 면에 새로 추가를 진행한다. 쓰고 나니 무슨소리인지 애매한데... 직접 그리면서 해야 이해가 쉬울 것 같다.

O(n)으로 해결