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

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

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

sum <- sum + A[i] * A[j]; 코드의 수행 횟수와, 그 수행 횟수를 다항식으로 나타낼 때의 최고차항 차수를 출력하는 문제.

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    long n;
    cin >> n;
    cout << n*n << endl << 2;
}

해당 코드는 이중 for문안에 위치해 있다.

더군다나, 두 for문 모두 1~n까지의 반복을 하고 있으므로, 해당 코드는 n * n 번을 수행하게 되는 것이다.

이때, 오버플로우가 발생하지 않도록 long으로 선언해야함을 주의하자.(입력 조건 : 1<= n <= 500000)

그리고 n*n 번을 수행한다는 것은, 이를 다항식으로 나타내면 n^2, 즉 최고차항의 차수는 2가 된다.