[백준 5724] 파인만 (C#, C++) - soo:bak

문제 링크

5724 - 파인만

설명

N × N 크기의 정사각형 격자에서, 서로 다른 크기의 정사각형이 총 몇 개인지를 계산하는 문제입니다.

즉, 1 × 1, 2 × 2, ..., N × N 크기의 정사각형이 격자 내에서 몇 개씩 등장하는지를 모두 합산해야 합니다.

예를 들어 N = 2일 경우:

• 1 × 1 정사각형은 총 4개 (2×2)
• 2 × 2 정사각형은 총 1개

→ 총합은 5개입니다.

접근법

• 각 정사각형 크기 k × k는,
  N × N 격자 안에서 (N - k + 1)^2 개 만들 수 있습니다.
  • 이는 N × N 정사각형 격자에서, 한 변의 길이가 k인 정사각형은 각 행과 각 열에서 N - k + 1개씩 배치할 수 있기 때문입니다.
• 따라서, 모든 가능한 크기의 정사각형을 전부 고려하려면, 이 값을 k = 1부터 N까지 모두 더해야 하며,
  그 총합이 곧 서로 다른 정사각형의 개수가 됩니다.

• 이는 수학적으로 다음과 같이 정리됩니다:

  \[\sum_{k=1}^{N} k^2 = \frac{N(N+1)(2N+1)}{6}\]

참고 : 자연수 제곱합 공식의 원리와 유도 과정 - soo:bak

Code

C#

using System;

class Program {
  static void Main() {
    while (true) {
      int n = int.Parse(Console.ReadLine());
      if (n == 0) break;
      int res = n * (n + 1) * (2 * n + 1) / 6;
      Console.WriteLine(res);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  while (cin >> n && n)
    cout << n * (n + 1) * (2 * n + 1) / 6 << "\n";

  return 0;
}