백준 24267번

백준 24267번을 풀어보았다.

 

앞서 풀어본 24262~24266번과 유사하지만 수행 횟수를 구하는 데 보다 수학적인 사고를 요한다.

 

먼저 정답 풀이는 아래와 같다.

let n = BigInt(require('fs').readFileSync('/dev/stdin').toString())

console.log((n*(n-1n)*(n-2n)/6n).toString())
console.log(3)

 

수행 횟수를 구하는 방법은 크게 3가지로 정리해보았다.

 

1. 문제 상황 그대로 식 세우기

 

문제 상황 그대로 식을 세워보면 아래와 같다.

이를 n에 대해 정리하여 수행 횟수를 구할 수 있다. 

 

2. 나열해보며 규칙 발견하기

 

주어진 범위 내에서 직접 나열해보며 규칙을 발견해보면 아래와 같다.

마지막 시그마를 n에 대해 정리하여 수행 횟수를 구할 수 있다.

 

이때, 꼭 위와 같은 방법이 아니어도 규칙을 찾을 수 있는 방법은 다양하다.

 

3. 조합적 사고

 

문제 상황을 잘 들여다보면 i, j, k는 1부터 n까지의 정수 중 중복되지 않게 3개의 정수를 선택하는 상황과 동일하다.

 

따라서 nC3을 n에 대해 정리하여 수행 횟수를 구할 수 있다.

 

 

위의 세 가지 방법 중 하나를 이용하여 수행 횟수를 구하면 간단하게 해결되는 문제였다.

 

다만 number 자료형이 아닌 bigint 자료형을 사용해야 한다는 사실만 유의하자.

 

참고) 백준 24266번