(24267) 알고리즘 수업 - 알고리즘의 수행 시간 6

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

단계별로 풀어보기

11단계(시간 복잡도) 6번째

 

 

 

2중for문이었던 수행 시간 4처럼 풀기엔 굉장히 헷갈리므로 수학적으로 접근해보자.

3중for문에서 i, j, k의 관계를 살펴보면 1≤i<j<k≤n라고 할 수 있으며, 마지막 for문 안쪽(코드1)은 이 부등식을 만족하는 모든 (i, j, k)의 수만큼 실행된다.

이 경우의 수는 1부터 n까지의 숫자 중 중복 없이 3개를 뽑아 크기 순서대로 i, j, k에 할당하는 경우와 같으므로 nC3이다.

 

 

 

#include <iostream>
using namespace std;

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