[백준 14545] Square (C#, C++) - soo:bak

문제 링크

14545번 - Square

설명

길이가 n 인 격자무늬 정사각형 안에 포함될 수 있는 모든 정사각형의 개수를 구하는 문제입니다.

먼저, 길이가 n 인 격자무늬 정사각형 안에서 만들 수 있는 정사각형의 개수는 다음과 같습니다.

• 길이가 1 인 정사각형 : n² 개
  
• 길이가 2 인 정사각형 : (n - 1)² 개
  
• 길이가 3 인 정사각형 : (n - 2)² 개
  
• ...
  
• 길이가 n 인 정사각형 : 1 개
  

이를 일반화하면 길이가 n 인 격자무늬 정사각형 안에서 만들 수 있는 길이가 i 인 정사각형의 개수는 (n - i + 1)² 입니다.

따라서 이들을 모두 합하면 전체 정사각형의 개수를 얻을 수 있으며, 다음과 같을 수열을 이룹니다.

1² + 2² + 3² + … + n²

이를 일반화하면 길이가 n 인 격자무늬 정사각형 안에 포함될 수 있는 모든 정사각형의 개수는 n * (n + 1) * (2n + 1) / 6 입니다.

각 테스트 케이스에 대해 입력받은 격자무늬 정사각형의 길이에 대하여 위 수식을 이용한 계산한 결과값을 출력합니다.

---

Code

[ C# ]

namespace Solution {
  class Program {
    static void Main(string[] args) {

      var p = int.Parse(Console.ReadLine()!);
      for (int i = 0; i < p; i++) {
        var l = long.Parse(Console.ReadLine()!);
        Console.WriteLine(l * (l + 1) * (2 * l + 1) / 6);
      }

    }
  }
}

[ C++ ]

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

  int p; cin >> p;

  for (int i = 0; i < p; i++) {
    ll l; cin >> l;
    cout << l * (l + 1) * (2 * l + 1) / 6 << "\n";
  }

  return 0;
}