c# 백준 24265 알고리즘 수업 - 알고리즘의 수행 시간 4

문제 링크

풀이 과정

문제는 입력값 n에 따라서 이중 for문을 이루는데
첫 번째 for문은 n - 1 번 반복된다.
두 번째 for문은 첫 번째 for문의 n - i 만큼 반복되는데 이는
n - 1번 반복, n - 2번 반복, … , 2번 반복, 1번 반복 이런식으로 된다.

1 + 2 + 3 + … + n의 공식은 (n + 1) / 2 * n 이다

여기서는 n번까지가 아니라 n - 1 번까지 반복이니 다음과 같음 ((n + 1) - 1)/ 2

여기까지가 안쪽의 for문 과정이고 이 만큼을 바깥쪽의 for문이 n - 1 만큼 반복하니
다음과 같은 식이 만들어진다. ((n + 1) - 1)/ 2 * (n - 1)

이를 정리하면 (n^2 - n) / 2이고 이것이 바로 수행 횟수이며 최고차항 차수는 2가 된다.

전체 코드

class Program
{
    static void Main(string[] args)
    {
        long n = long.Parse(Console.ReadLine());

        Console.WriteLine((n*n - n) / 2);
        Console.WriteLine(2);

        // 이중 for문 중 안쪽의 for문은
        // n - 1번 실행 n - 2번 실행 n - 3번 실행 ... 1 번 실행
        // 이 말은 곧 ->  1 + 2 + ... (n - 2) + (n - 1) 

        // 1 + 2 + 3 + ... + n의 공식은 (n + 1) / 2 * n
        // 여기서는 n번까지가 아니라 n - 1 번까지 반복이니 다음과 같음 ((n + 1) - 1)/ 2

        // 그런데 이 과정이 n - 1번 실행됨  ((n + 1) - 1)/ 2 * (n - 1)
        // 식을 풀면
        // n(n - 1) / 2
        // (n^2 - n) / 2 최고차항 2 
    }
}