BOJ 1540 : 정사각형의 개수

• 문제 링크 : boj.kr/1540
• 난이도 : G3
• 태그 : 그리디, 수학

1540번: 정사각형의 개수

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;

    int ans = 0;
    int i;
    for(i = 2; i*i <= n; i++) {
        ans += (i-1)*(i-1);
    }
    i -= 1;
    n -= i*i;
    for(int j = 0; j < i; j++) {
        if(!n) break;
        ans += j;
        n -= 1;
    }
    for(int j = 0; j < i; j++) {
        if(!n) break;
        ans += j;
        n -= 1;
    }
    cout << ans;

    return 0;
}

---

풀이

구현에는 그리디가 필요없지만 아이디어를 떠올리는데에는 그리디적인 발상이 필요하다.

N개의 점을 찍으며 매 순간마다 최선의 위치에 점을 찍는다고 한다면 다음의 순서대로 점을 찍게 된다.

\begin{equation}
    \begin{matrix}
    \text{10} & \text{11} & \text{12} & \text{16}  \\
    \text{5} & \text{6} & \text{9} & \text{15}  \\
    \text{2} & \text{4} & \text{8} & \text{14}  \\
    \text{1} & \text{3} & \text{7} & \text{13}  \\
    \end{matrix}
\end{equation}

매 순간 점을 가장 많은 정사각형을 확보할 수 있거나, 정사각형을 확보하지 못한다면 그럴 수 있는 위치에 찍게 된다.

예를 들어 12번째 점을 찍을 때에는, 두 개의 정사각형이 확보되고, 그런 위치는 11번째 점을 찍은 상태에선 유일하다.

위의 논리를 따라 점을 찍어보면, 전체적인 점의 모양이 정사각형이 되도록 하나의 변을 따라가며 점을 찍는다는 것을 알 수 있다.

따라서 n을 넘지 않는 점을 가지는 정사각형을 미리 그려서 정사각형의 수를 구해놓고, 점을 찍으며 세어보면 답을 구할 수 있다.