24265 번 : 알고리즘 수업 - 알고리즘의 수행 시간 4

문제는 다음과 같습니다.

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

24265번: 알고리즘 수업 - 알고리즘의 수행 시간 4

 

풀이 코드는 다음과 같습니다.

#include <iostream>
using namespace std;


int main()
{
	long long n;
	cin>>n;
	cout<<(n*(n-1))/2<<"\n"<<2;
	return 0;
}

코드를 보면서 설명드리겠습니다.

이중으로 for문이 있는 것은 다르지 않지만 범위가 살짝 다릅니다. 

맨 처음 있는 for문은 1부터 n-1까지, 그 안에 있는 for문은 i부터 n까지입니다.

이 구문을 실행하게 되면 1+2+3+4+.....+(n-2)+(n-1)이며 이는 n*(n-1)/2입니다.

또한 시간복잡도는 O(n^2)이므로 차수는 계속 2를 출력하면 됩니다.