백준 - 24267 .알고리즘의 수행시간

문제 설명

오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.

MenOfPassion 알고리즘은 다음과 같다.

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 2
        for j <- i + 1 to n - 1
            for k <- j + 1 to n
                sum <- sum + A[i] × A[j] × A[k]; # 코드1
    return sum;
}

입력

첫째 줄에 입력의 크기 n(1 ≤ n ≤ 500,000)이 주어진다.

출력

첫째 줄에 코드1 의 수행 횟수를 출력한다.

둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.

 

import java.io.*;

public class Main{
    
    public static void main(String [] args)throws IOException{
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long sum = 0;
        for(int i = 1; i<n ; i++){
           sum += ((long)i*(i-1))/2;
        }
        System.out.println(sum);
        System.out.print(3);
    }
    
}

---

리팩토링

import java.io.*;

public class Main{
    
    public static void main(String [] args)throws IOException{
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        System.out.println((long)(n*(n-1)*(n-2))/6);
        System.out.print(3);
    }
    
}

 

1. 솔직히 아무리 공식으로 연관지을래도 떠오르지 않았음.. ㅎ.

검색해보니 확률과 통계할 때 배웠던 조합 공식에서 나온 답이였음. 

이 조합 공식에서 

해당 문제는 항상 r이 3이므로(i,j,k)

r에 3 값을 대입하고 

팩토리얼을 전개, 분모 분자 약분을 하면

최종적으로 (n*(n-1)*(n-2))/6 공식이 나온다. 

리팩토링 수정 후 시간, 메모리, 코드길이 모두 줄었음!