[JAVA] 백준 14929 합정렬

 

 

14929번: 귀찮아 (SIB)

문제

다음을 구하시오.

풀이

글로 작성하니 뭔가 규칙이 보였다.

규칙은 다음과 같다.

 

 

N이 4인 경우 12, 13, 23은 이전의 3에 대한 합이고 나머지 1-4, 2-4, 3-4는 (1 + 2 + 3)*4이기 때문에 1~3까지의 합배열에 4를 곱한 것이었다.

처음에 풀었을 때이다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt()+1;

        int[] O = new int[N];
        int[] A = new int[N];
        long[] S = new long[N];

        if(N > 1){
            for(int i=1; i<N; i++){
                O[i] = sc.nextInt();
                A[i] = A[i-1] + O[i];
            }

            //S[2] = O[1] * O[2];
            for(int i=2; i<N; i++){
                S[i] = S[i-1] + A[i-1]*O[i];
            }

            System.out.println(S[N-1]);
        }else{
            System.out.println(0);
        }

    }
}

이를 리팩토링하기 위해 좀 더 식을 작성해서 구해보았다.

만약 N = 3이라면

0 + 1 * 2 + 1 * 3 + 2 * 3

만약 N = 4라면

0 + 1 * 2 + 1 * 3 + 2 * 3 + 1 * 4 + 2 * 4 + 3 * 4

여기서 2, 3, 4로 묶어내면

(1)2 + (1 + 2)3 + (1 + 2 + 3)*4

합 배열에 대해서 N까지 곱해주면 구해줄 수 있다!

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt()+1;

        int[] O = new int[N];
        int[] A = new int[N];

        for(int i=1; i<N; i++){
            O[i] = sc.nextInt();
            A[i] = A[i-1] + O[i];
        }

        long sum = 0;
        for(int i=1; i<N; i++){
            sum += A[i-1]*O[i];
        }

        System.out.println(sum);
    }
}

해결