[백준 24265] 알고리즘 수업 - 알고리즘의 수행 시간 4

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

문제 분석

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

코드

#include <iostream>
 using namespace std;

 int main()
 {
     long a;

     cin >> a;

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

해석

주어진 MenOfPassion함수는 반복문도 입력받은 값이 0이 될때까지 -1을 하며 수를 더하는 함수이므로
(입력이 7이 들어오면 7 + 6 + 5 + 4..... + 1)
시간복잡도는
(n - 1) * n / 2
이다.

MenOfPassion함수의 시간복잡도를 O(n^2)로 표현 할 수 있기 때문에 이 시간복잡도의 차수는 입력받은 값에 상관없이 2이다.

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