[C#] 24265번: 알고리즘 수업 - 알고리즘의 수행 시간 4

목차

---

백준 단계별로 풀어보기

25.10.01

11단계: 시간 복잡도

24265번: 알고리즘 수업 - 알고리즘의 수행 시간 4

문제 링크 : https://www.acmicpc.net/problem/24265

 

문제 풀이

>> 문제를 풀기 위해 알아야 할 개념

- 등차수열에서 두 수 사이의 합

: 두 수를 x 와 y라고 하고 두 수 사이의 수의 개수를 n이라고 할 때, x 와 y 사이의 합은 'n × (x + y) / 2' 이다.

 

※ 참고한 블로그

모르면 못푸는 수학 공식들(계속 수정)

 

>> 문제에 나온 알고리즘 해석

: 문제에 나온 MenOfPassion 알고리즘은 다음과 같다.

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;
}

• 배열 'A[]' 과 'n' 을 입력받는다.
• 'sum'에 0을 대입한다.
• for 반복문을 이중으로 사용하는데, 첫 for문은 1부터 n - 1까지 반복하고 두 번째 for문은 i + 1부터 n까지 반복하며 sum에 A[i] × A[j] 값을 더하고 sum에 대입한다. --> i가 커질수록 두 번째 for문이 반복하는 횟수가 줄어든다.
• sum을 반환한다.

 

>> 풀이

: 코드 1의 수행 횟수를 계산하기 위해 예를 들어보자.

• i가 1일 때 : j는 2부터 n까지 즉, n - 1회
• i가 2일 때 : j는 3부터 n까지 즉, n - 2회
• i가 n - 1일 때 : j는 n부터 n까지 즉, 1회

--> 따라서 코드 1의 수행 횟수는 1 + 2 + 3 + ... + n - 1 회 수행된다. 이는 등차수열이기에 1부터 n - 1회까지의 합은 공식에 따라 (n - 1) × n / 2 이다. 즉, f(n) = (n² - n) / 2  이므로 최고 차항의 차수는 2이다.

1. 입력값을 받아 ulong값으로 변환한다. --> n의 최댓값이 500,000 이므로 n² 이 int의 범위보다 커질 수 있기에 ulong으로 변환
2. (n - 1) × n / 2 값과 2를 줄바꿈과 함께 출력한다.

 

정답 코드

class Backjoon
{
    static void Main(string[] args)
    {
        ulong input = ulong.Parse(Console.ReadLine());
        Console.Write($"{(input - 1) * input / 2}\n2");
    }
}