[코딩테스트] 벡준 - 알고리즘 수업 - 알고리즘의 수행 시간 4

백준 - 알고리즘 수업 - 알고리즘의 수행 시간 4 24265번 [5일차]

시간제한	메모리 제한
1초	512MB

문제

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

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

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

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

 

입력

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

 

 

출력

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

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

 

나의코드

package day5;

import java.io.*;

public class Solution1 {

    // 알고리즘 수업 - 알고리즘의 수행 시간 4 24265번
    // int [] A = 0;
    // int n
    // int sum = 0
    // for(i =1;i < n-1; i++){
    //  for(int j = i+1; j < n){
    //      sum = sum +A[i] * A[j]
    //  }
    // }
    // n=7
    // 6+5+4+3+2+1

    // (n-1) + (n-2) + ... + (n-n-1)
    // n ~ 1까지의 합 => n * (n+1) / 2
    // n-1 ~1 까지의 합 => n *(n-1) / 2
    // O((n^2-n) / 2) => n^2
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        long result = (long) n *(n-1)/2;

        bw.write( result+ "\n" + 2);
        br.close();
        bw.close();
    }

}

 

일단 코드에 규칙을 찾았다.

n=7 일때
i=1 / j =2~7 까지 6개
i=2 / j =3~7 까지 5개
i=3 / j =4~7 까지 4개
i=4 / j =5~7 까지 3개
i=5 / j =6~7 까지 2개
i=6 / j =7 까지 1개
6+5+4+3+2+1 = 21

n~1 까지 숫자의 합을 구하는 규칙!  : 등차수열의 합 = n * (n-1)/2

 

위의 규칙을 봤을때는 6~1까지의 합을 구하면된다.

=> (n-2) * (n-1) / 2

 

 

그리고 최고차항의 차수를 출력 => 빅오표기법으로 최악의 시간을 구하는거였다

O((n^2-n) / 2) 

상수를 제거하고  n^2 가나온다