[백준] 24267:알고리즘 수업-알고리즘의 수행 시간 6 (자바)

---

도저히 감이 잡히지 않아서 다른 블로그를 참고했다.

---

방법 1. 시그마 공식 사용

$\displaystyle\sum_{i=1}^{n}{1}$ 이 식의 반복 횟수는 $n-1+1$ 이다.
-> 윗끝 - 아랫끝 + 1 이라고 볼 수 있다.

해당 문제의 알고리즘을 시그마 식으로 나타내면,
$\displaystyle\sum_{i=1}^{n-2}\displaystyle\sum_{j=i+1}^{n-1}\displaystyle\sum_{k=j+1}^{n}1$ 이다.

순차적으로 시그마 공식을 적용시켜 보겠다.
$\displaystyle\sum_{i=1}^{n-2}\displaystyle\sum_{j=i+1}^{n-1}(n-j)$

$\displaystyle\sum_{i=1}^{n-2}\frac{(n-i-1)(n-i)}2$

$(n)(n-1)(n-2)\over 6$ 으로 정리할 수 있다.

방법 2.조합 공식 이용

(i,j,k)에 값을 넣어보며 규칙을 찾아보면
(1,2,3)...(1,2,7)
(2,3,4)...(2,3,7)
... (5,6,7) -> 중복되지 않는 세 숫자가 나타난다.

$_nC_k = \frac{n!}{(n-k)!*k!}$

$_nC_3 = \frac{(n)(n-1)(n-2)} 6$

위 식과 동일하다는 것을 알 수 있다.

---

package buffer;

import java.io.*;
import java.util.StringTokenizer;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long n = Long.parseLong(st.nextToken());
        
        BigInteger result = new BigInteger(String.valueOf(n*(n-1)*(n-2)/6));



        System.out.println(result.toString() + "\n" + 3);
    }
}