https://www.acmicpc.net/problem/24267
24267번: 알고리즘 수업 - 알고리즘의 수행 시간 6
오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시
www.acmicpc.net
2가지 방법으로 수행시간을 측정할 수 있다.
1. 수열의 합으로 생각
수열 합 계산을 통해,
$ \frac{n(n-2)(n-1)}{6} $의 값을 얻을 수 있다.
이 값을 유심히 살펴본 결과, nC3, n개의 숫자 중 3개를 선택하는 경우의 수와 동일하다.
위 수열의 결과와 조합을 이용한 결과는 다음과 같다.
#include <iostream>
using namespace std;
int main()
{
long long n;
cin >> n;
cout << (n * (n - 1) * (n - 2)) / 6 << '\n'
<< 3;
}