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

 

이번 알고리즘도 O(n^2)으로 차수는 2

횟수 부분이 좀 다른데

i부터 n-1까지돌면서 i+1부터 n까지 돌린다.

예를 들어 n이 7이라고 하면

i가 1일때 > 6

i가 2일때 > 5

i가 3일때 > 4

i가 4일때 > 3

i가 5일때 > 2

i가 6일때 > 1

 

따라서 6+5+4+3+2+1 = 21이 되는것이다.

식을로 풀어쓰면 n(n-1)/2인데

이는 n개의 숫자중에서 순서 상관없이 원소2개를 구하는 공식과 같다.

 

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

 

따라서 첫번째줄에 n * (n - 1) / 2을 출력해주고

두번째줄에 2를 출력해주자.