시간복잡도 BOJ 24265

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

 

$$ \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}1=\sum_{i=1}^{n-1}(n-i)=n(n-1)-(n-1)\times \tfrac{n}{2}=\frac{n(n-1)}{2} $$

 

#include <stdio.h>

int main()
{
    long long n;
    scanf("%lld", &n);
    printf("%lld\n2", (n-1)*n/2);
}