[백준 24267] 알고리즘 수업 - 알고리즘의 수행 시간 6

🔗문제 풀러가기
단계별로 풀어보기 단계 11의 6번째 문제이다.

문제 분석

주어진 MenOfPassion의 수행 횟수를 출력하고 시간 복잡도의 차수를 출력하면 되는 문제이다.

코드

#include <iostream>
 using namespace std;

 int main()
 {
     long a;

     cin >> a;

     cout << (a - 2) * (a - 1) * a / 6 << endl << 3;
 }

해석

주어진 MenOfPassion함수는

주어진 코드는 n 의 크기에 따라 i = 1부터 n - 2까지,
그리고 그 안에서 j = i + 1부터 n - 1까지,
다시 그 안에서 k = j + 1부터 n까지 반복하면서
A[i] A[j] A[k] 의 합을 구하여 출력

하는 코드이다.

이는 시그마 합 공식과 같으므로

따라서

수행횟수는 (a - 2) (a - 1) a / 6,
수행 시간은 O(n^3) 이다.

추가로 입력값의 조건이 최대 500,000이므로 자료형을 long으로 해주어야 한다.