[java] 백준 2721번 삼각수의 합

문제에서 T(n)은 1부터 n까지의 합, T(4) = 1+2+3+4, 즉 T(4) = 10

W(n) = Sum[k=1..n; k*T(k+1)]

 

좀 쉽게 풀어서 쓰자면 W(4)일 때 식은 이렇게 나온다.

W(4) = 1*T(2) + 2*T(3) + 3*T(4) + 4*T(5)

 

T를 좀더 쉽게 풀어쓰면

W(4) = 1*(1+2) + 2*(1+2+3) + 3*(1+2+3+4) + 4*(1+2+3+4+5)

W(4) = 3 + 12 + 30 + 60 = W(4) = 105가 된다.

 

처음에 문제를 봤을 때 이게 뭔 소린가 싶었다. 필자는 공부에 뜻이 없어 전과목을 포기했다... ㅋㅋㅋ 오로지 게임에만...

일단 직접 써봤다... 문제 이해도 안되고 어떻게 입력이 4일 때 출력이 105가 나오는지도 몰랐다.

이 문제의 공식도 어제 풀었던 시그마 문제랑 식이 비슷하다.

[java] 백준 2355번 시그마

 

공책을 보거나 위에 문제풀이를 보면 규칙이 있다. 1~n까지 합. 시그마 문제에서 썼던 가우스 덧셈 공식이랑 비슷하다. 아니 좀 더 쉽다.

 

그래서 나온 식은 n x ( (n+1) x (n+2) ) / 2 이고 누적을 시켜주면 된다. 이 공식을 구하기 위해서 거꾸로 풀었다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            int n = sc.nextInt();
            int tot = 0;
            for (int j = 1; j <= n; j++) {
                tot += j * (j + 1) * (j + 2) / 2;
            }
            System.out.println(tot);
        }
    }
}