백준문제풀이 11단계 시간 복잡도(6) 24267번 알고리즘 수업 - 알고리즘의 수행 시간 6 (C#)

 

오늘의 알고리즘.

이번에도 삼중 for문.

차수는 3차이고 실행횟수를 자세히 살펴보면 저번문제와는 조금 다르다.

 

저번에 풀었던 4번 문제와 비슷한데

n개의 숫자중에서 i,j,k새개의 원소를 중복없이 뽑는 거니까

nC3 = n*(n-1)*(n-2)/6을 해주면 된다.

using System;
class BackJoon
{
    static void Main(string[] args)
    {
        long n = long.Parse(Console.ReadLine());
        Console.WriteLine(n*(n-1)*(n-2)/6);
        Console.WriteLine(3);
    }
}

 

저번 문제와 같이 for문을 이용해 누적합을 구해도 답은같다.

 

using System;
class BackJoon
{
    static void Main(string[] args)
    {
        long n = long.Parse(Console.ReadLine());
        long sum = 0;
        for (int i = 2; i < n; i++)
            sum += i * (i - 1) / 2;
        Console.WriteLine(sum);
        Console.WriteLine(3);
    }
}