[백준] 24264번: 알고리즘 수업 - 알고리즘의 수행 시간 3 (JAVA)

문제: https://www.acmicpc.net/problem/24264

문제 접근

MenOfPassion에 입력값을 넣어 수행 횟수와 시간복잡도의 최고차항 차수를 구하는 문제였습니다.

(혹시라도 빅오 표기법에 대해 궁금하시다면 저번 글을 참고해 주세요!)

 

우선, MenOfPassion 알고리즘은 다음과 같습니다.

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

1. 배열과 입력값이 주어진다.
2. sum을 0으로 초기화한다.
3. 첫 번째 for문: i를 1부터 n까지 수행 (n번)
4. 두 번째 for문: j를 1부터 n까지 수행(n번)
5. A[i] x A[j] 와 sum을 더하여 sum에 저장한다.
6. for문이 끝나면 sum 반환

이때 실행 결과에 영향을 미치는 것은 중첩 for문입니다.

• i = 1 일 때, j는 1부터 n까지 수행 
• i = 2 일 때, j는 1부터 n까지 수행
• i = 3 일 때, j는 1부터 n까지 수행
• i = n 일 때, j는 1부터 n까지 수행

즉, 수행 횟수는 (j가 수행되는 횟수) x (i가 수행되는 횟수) 로 n² 이며, 시간 복잡도는 O(n²)이므로 두 번째 줄에는 2를 출력하면 됩니다.

 

또한 이번 문제에서는 코드를 짤 때 입력값의 자료형을 주의해주셔야 합니다.

입력 조건을 보면 n은 최대 500,000까지 입력될 수 있며, 수행 횟수는 최대 500,000 x 500,000 = 250,000,000,000 가 될 수 있습니다. 하지만 이는 int의 범위(약 21억)를 넘어섭니다.

따라서 오버플로우 방지를 위해 long을 사용해야 합니다. (저는 int로 코드를 작성해서 한 번 틀렸습니다 ㅠㅠ)

전체 코드

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());
        bw.write(n * n + "\n2");
        bw.close();
    }
}

 

앞으로는 조건 같은 것을 더 꼼꼼히 봐야될 것 같습니다.

 

읽어주셔서 감사합니다!