[24267] 백준 문제풀이 - 알고리즘 수업 - 알고리즘의 수행 시간 6

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

문제

오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.

MenOfPassion 알고리즘은 다음과 같다.

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 2
        for j <- i + 1 to n - 1
            for k <- j + 1 to n
                sum <- sum + A[i] × A[j] × A[k]; # 코드1
    return sum;
}

입력

첫째 줄에 입력의 크기 n(1 ≤ n ≤ 500,000)이 주어진다.

출력

첫째 줄에 코드1 의 수행 횟수를 출력한다.

둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.

풀이

이번 코드도 알고리즘 수업 시간 시리즈와 비슷하게 굉장히 짧은 코드로 끝난다. 하지만 이 짧은 코드를 적기 위해서는 시그마란 개념에 대해 알아야한다. 아래 링크에 시그마에 대해 정리해보았으니 모르고 있었다면 공부해보자.

[수학개념] 시그마의 뜻과 성질

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 2
        for j <- i + 1 to n - 1
            for k <- j + 1 to n
                sum <- sum + A[i] × A[j] × A[k]; # 코드1
    return sum;
}

에서 진행은 다음과 같다.

1. i가 1 ~ n-2 까지 반복
2. j가 i+1 ~ n-1까지 반복
3. k가 j+1 ~ n까지 반복하며 sum += A[i] * A[j] * A[k]의 합을 수행함.

시그마로 나타내보면

1. $\displaystyle\sum_{i=1}^{n-2}{}\sum_{j=i+1}^{n-1}{}\sum_{k=j+1}^{n}{1} = \sum_{i=1}^{n-2}{}\sum_{j=i+1}^{n-1}{(n-j)}$ $(n-j)$가 나온 이유는 시그마에서 상수항이 나올 경우

1. 상수만 있는 시그마는 상수는 단순 곱셈으로 바꿀 수 있다. $\displaystyle\sum_{k=1}^{n}{c} = c·n$ 주의해야 할 점은, $\displaystyle\sum_{k=3}^{n}{c} = c·n$과 같은 시그마가 나온다면 k가 3부터 시작했으므로 정답은 $c·n$이 아닌 $c·(n-2)$이다.

라는 성질이 있다. 정확히는 항의 갯수만큼 곱하는 것이기 때문에 $\displaystyle\sum_{k=j+1}^{n}1$ 은 $1·(n-(j+1)-1)$ 이므로 $n-j$이 됨을 알 수 있다.

1. $\displaystyle\sum_{i=1}^{n-2}{}\sum_{j=i+1}^{n-1}{(n-j)} = \sum_{i=1}^{n-2}{}(\sum_{j=i+1}^{n-1}{n}-\sum_{j=i+1}^{n-1}{j})$ 더하기 빼기가 자유로운 성질을 이용해서 나눠준다.
   

2. $\displaystyle\sum_{i=1}^{n-2}{}(\sum_{j=i+1}^{n-1}{n}-\sum_{j=i+1}^{n-1}{j}) = \sum_{i=1}^{n-2}{}{\sum_{j=1}^{n-1}{n}-\sum_{j=1}^{i}{n} - (\sum_{j=1}^{n-1}{j}-\sum_{j=1}^{i}{j})} $ 아래 시그마의 시작 수를 1로 만들 수 있다로 풀이할 수 있다.

   1. 시그마의 시작 수를 1로 만들 수 있다. $\displaystyle\sum_{k=m}^{n}{a_k} = \sum_{k=1}^{n}{a_k} - \sum_{k=1}^{m-1}{a_k} (단, n>m>1)$ k=1로 만드는 이유는 k가 1일 경우 계산하기가 편하기 때문이다. 증명은 일일이 다 풀어보면 증명할 수 있다. 이 변환공식 또한 유용하게 쓰인다.

1. $\displaystyle\sum_{i=1}^{n-2}{(n(n-1)-n·i-(\frac{n(n-1)}{2}-\frac{i(i+1)}{2})}$ 시그마의 공식을 이용해서 풀어낼 수 있다

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

3. $\frac{\frac{(n-1)(n-2)(2n-3)}{6}+(1-2n)\frac{(n-1)(n-2)}{2}+n(n-1)(n-2)}{2} = \frac{n(n-1)(n-2)}{6}$

마지막 풀이까지 오는 길이 험하고도 아득했다. 이 문제를 풀이하느라 시그마에 대해서 다시 한번 찾아보고 여러 방법도 찾아보았다. 결국 정답은 (n * (n - 1) * (n - 2) // 6)라는 간단한 코드가 나온다. 또 여러 방법도 찾아본 결과 이렇게 어려운 풀이과정이 아닌 단순히 i, j, k를 1부터 n까지 숫자 중에 3가지를 뽑아 중복 없이 크기 순으로 작성하는 경우의 수, 즉 고등과정의 확률과 통계에서 조합을 구하는 방법 \(_nC_r=\frac{n!}{r!(n-r)!}\) 으로 쉽게 풀 수 있다..

실제로 풀어보면

\(_7C_3 = \frac{7!}{3!4!} = \frac{7*6*5*4*3*2*1}{(3*2*1)(4*3*2*1)}\) 에서 $4321$을 약분하면 $\frac{765}{32*1}$, 35가 나와서 정답이다

n = int(input())

print((n * (n - 1) * (n - 2) // 6))
print(3)