백준 24266 알고리즘 수업 - 알고리즘의 수행 시간5 [JAVA]

문제 해석

• 오늘 포스트할 문제 또한 거의 이번주 내내 포스트했던 알고리즘 수행 시간 1, 2, 3, 4를 이은 문제이다.
• 주어진 알고리즘 코드를 분석하고 콘솔로부터 입력받은 n에 대한 수행 횟수를 첫번째 줄에 출력하고 두번째 줄에는 수행시간의 차수를 출력하면 된다.

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

알고리즘 코드 -> JAVA로

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        long n = Long.parseLong(br.readLine());
        br.close();

        int count = 0; //수행 홧수 저장하는 변수

        for(int i  = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                for(int k = 1; k <= n; k++){
                    count++;
                }
            }
        }

        System.out.println(count);
    }
}

• 이해하기 편하게 내게 익숙한 JAVA로 작성해보았다.
• 해당 알고리즘은 오히려 전 POST보다 간단했다.

  i = 1일때
  - j = 1 ~ n까지 반복
  - - j가 1일때
  - - - k가 1 ~n까지 반복
  이러한 과정이 i가 1부터 n까지 반복한다.
  즉, k는 j를 기준으로 1~n까지 반복하고, j는 i를 기준으로 1~n까지 반복한다.

• 따라서, 이번 문제의 수행 횟수는 n^3이고 수행 시간은 O(n^3)이다.

코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        long n = Long.parseLong(br.readLine());
        br.close();

        bw.write(n*n*n + "\n" + 3);
        bw.flush();
        bw.close();
    }
}

• 여기서, 고려해야할 점은 입력크기 n이 1보다 크거나 같고 500,000보다 작거나 같다. 3제곱을 표현해야하기 때문에 자료형을 잘 살펴야한다!
• 최대 500,000 500,000 500,000 = 1.25e+17(=125,000,000,000,000,000)이고, long 자료형이 최대 9,223,372,036,854,775,807까지 표현가능하니까 입력받은 n의 자료형은 최소 long이어야한다.

결과

느낀점