24267 번 : 알고리즘 수업 - 알고리즘의 수행 시간 6

문제는 다음과 같습니다.

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

24267번: 알고리즘 수업 - 알고리즘의 수행 시간 6

 

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

#include <iostream>
using namespace std;


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

코드 1만 보아서는 어렵게 보일 수 있지만 예시를 들어 설명드리겠습니다.

n이 5라고 가정할 때,

i=1 일 때, j는 2,3,4가 가능하고

이때 j=2일 때, k=3,4,5 가 가능하게 됩니다.

이 순서는 1부터 n까지 3가지의 숫자를 중복 없이 뽑는 그냥 우의 수임을 알 수 있습니다.

따라서 nC3이기 때문에 nC3을 처음에 출력해주면 됩니다.