[백준] 24264번: 알고리즘 수업 - 알고리즘의 수행 시간 3 | C++ 풀이

# 문제

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

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;
}

이번에는 이중 for문이다. 배열의 i번째, j번째 원소를 더해 반환하는 알고리즘이다.

코드를 살펴보면 어떤 n을 넣더라도 코드 1은 n²회 수행, 수행 시간은 n²에 비례함을 알 수 있다.

따라서 시간 복잡도는 O(n²)이고, 항상 n²과 2를 개행하여 출력해주면 끝!

 

 

#include <iostream>
using namespace std;

int main(){
    long long n;
    cin >> n;
    cout << n*n << '\n' << 2;
    return 0;
}

다만 코드를 짤 때 주의해야 할 점은 n의 자료형을 설정하는 것이다.

n은 최대 500,000이 입력될 수 있으므로 이의 제곱을 고려해 자료형을 long long으로 설정해주었다.

이 점만 빠뜨리지 않는다면 이번에도 코드는 아주 간단하게 짤 수 있다!

 

 

 

 

 

---

 

 

24264번: 알고리즘 수업 - 알고리즘의 수행 시간 3