처음 n개 자연수의 제곱의 합과 합의 제곱의 차이 구하기

문제 정의

주어진 숫자 n에 대해, 처음 n개 자연수의 제곱의 합과 합의 제곱 사이의 차이를 구하는 프로그램을 작성해야 합니다.

예시

n = 3

처음 세 개 수의 제곱의 합
= 3x3 + 2x2 + 1x1
= 9 + 4 + 1
= 14

처음 세 개 수의 합의 제곱
= (3 + 2 + 1)x(3 + 2 + 1)
= 6x6
= 36

차이
= 36 - 14
= 22

접근 방법

이 문제는 반복문 없이 잘 알려진 수학 공식을 활용하면 O(1) 시간 복잡도로 해결할 수 있습니다.

• 제곱의 합: 처음 n개 자연수의 제곱의 합은 n(n+1)(2n+1)/6 공식으로 구할 수 있습니다.
• 합의 제곱: 처음 n개 자연수의 합은 n(n+1)/2 공식으로 구하고, 그 값을 다시 제곱하면 됩니다.
• 차이: 두 값의 절댓값 차이를 반환하면 원하는 결과를 얻을 수 있습니다.

Java 구현 코드

다음은 위 공식을 활용하여 차이를 계산하는 Java 프로그램입니다.

public class JavaTester {
   public static int difference(int n){
      // n개 자연수의 제곱의 합
      int sumSquareN = (n * (n + 1) * (2 * n + 1)) / 6;
      // n개 자연수의 합
      int sumN = (n * (n + 1)) / 2;
      // n개 자연수의 합의 제곱
      int squareSumN = sumN * sumN;
      // 두 값의 차이
      return Math.abs(sumSquareN - squareSumN);
   }
   public static void main(String args[]){
      int n = 3;
      System.out.println("Number: " + n);
      System.out.println("Difference: " + difference(n));
   }
}

출력 결과

Number : 3
Difference: 22

위 코드에서는 반복문을 사용하지 않고 공식만으로 계산하기 때문에, n이 커져도 성능 저하 없이 즉시 결과를 얻을 수 있다는 장점이 있습니다.