백준 - [단계별로 풀어보기 시간 복잡도] 24265 알고리즘 수업 - 알고리즘의 수행 시간 4

이번 문제는 기존의 시간 복잡도 문제와 달리 수학 공식을 활용하여 실행 횟수를 계산해야 하는 문제이다.
알고리즘 구조를 보면 이중 반복문이 사용되지만, 두 반복문의 실행 횟수가 서로 다르다.

for i = 1 to n-1
    for j = i+1 to n

예를 들어 n = 7일 때 i는 1부터 6까지 총 6번 반복된다. 그리고 j의 반복 횟수는 다음과 같이 줄어들게 된다.

i = 1 → j : 2 3 4 5 6 7  (6번)
i = 2 → j : 3 4 5 6 7    (5번)
i = 3 → j : 4 5 6 7      (4번)
i = 4 → j : 5 6 7        (3번)
i = 5 → j : 6 7          (2번)
i = 6 → j : 7            (1번)

따라서 j의 반복 횟수는 (n-1) + (n-2) + ... + 1이 된다. 이 합을 구하기 위해 등차수열의 합 공식을 사용할 수 있으며, 이를 정리하면 다음과 같다. 

n(n-1) / 2

추가로 이번 문제에서는 int 자료형을 사용하면 안 된다. 실행 횟수는 n(n-1)/2로 계산되며, n의 최대값이 매우 크기 때문에 결과값이 int 자료형의 범위를 초과할 수 있다. 따라서 오버플로우를 방지하기 위해 long 자료형을 사용하여 실행 횟수를 계산해야 한다.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp3
{
    internal class TimeComplexity
    {
        static void Main(string[] args)
        {
            //백준 24265 알고리즘 수업 - 알고리즘의 수행시간 4
            long n = long.Parse(Console.ReadLine());  //n의 최대값은 500,000이므로 실행 횟수가 int 범위를 넘어가기에 변수를 long을 사용해야 한다.
            Console.WriteLine((n - 1) * n / 2);   //등차수열의 공식을 사용해 실행 횟수 계산
            Console.WriteLine(2);   //이중반복문이므로 차수는 2 (가장 크게 증가하는 항 n^2이므로 O(n^2))
        }
    }
}

출력 결과