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

목차

---

백준 단계별로 풀어보기

25.10.03

11단계: 시간 복잡도

24267번: 알고리즘 수업 - 알고리즘의 수행 시간 6

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

 

문제 풀이

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

- 삼각수 (Triangular Number)

: 삼각수는 1부터 시작하는 연속된 자연수의 합을 나타내는 수이다. 이는 아래 그림과 같이 정삼각형 모양으로 배열된 물체의 개수와 같다.

--> 앞서 업로드한 '알고리즘 수업 - 알고리즘의 수행 시간 4' 에서 나온 첫 항이 1, 공차가 1인 등차수열의 합과 동일하다. 즉, 1부터 n까지의 합은 n(n + 1) / 2

(* 공차 : 연속하는 두 항 사이의 일정한 차이)

출처 : 위키백과

 

※ 참고 문서 - 위키백과

삼각수 - 위키백과, 우리 모두의 백과사전

 

- 삼각수들의 합

: 등차수열의 합과 같이 삼각수들로 이루어져있는 수열의 합을 구하면 된다.

--> 삼각수들의 합을 시그마로 표현했을 때 아래와 같이 풀이할 수 있다.

 

※ 시그마 합 공식

출처 : https://duckingracoon.tistory.com/3

 

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

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

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 2
        for j <- i + 1 to n - 1
            for k <- j + 1 to n
                sum <- sum + A[i] × A[j] × A[k]; # 코드1
    return sum;
}

• 배열 'A[]' 과 'n' 을 입력받는다.
• 'sum'에 0을 대입한다.
• for 반복문을 삼중으로 사용하는데, 첫 for문은 1부터 n - 2까지 반복하고 두 번째 for문은 i + 1부터 n - 1까지 반복하고 세 번째 for문은 j + 1부터 n까지 반복하며 sum에 A[i] × A[j] × A[k] 값을 더하고 sum에 대입한다.
• sum을 반환한다.

 

>> 풀이

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

• i가 1일 때 : j는 2부터 n - 1까지고 k는 3부터 n까지 즉, 1 + 2 + ... + n - 2 → (n - 2)(n - 1) / 2 회
• i가 2일 때 : j는 3부터 n - 1까지고 k는 4부터 n까지 즉, 1 + 2 + ... + n - 3 → (n - 3)(n - 2) / 2 회
• i가 n - 2일 때 : j는 n - 1부터 n - 1까지고 k는 n부터 n까지 즉, 1회

--> 따라서 코드 1의 수행 횟수는 1 + (n - 6)(n - 5) / 2 + (n - 5)(n - 4) / 2 + ... + (n - 2)(n - 1) / 2 회 실행된다. 이는 1부터 n - 2까지의 삼각수들의 합과 같으므로, 삼각수들의 합 공식에 따라 (n - 2)(n - 1)n / 6 이다. 즉, f(n) = (n³ - 3n² + 2n) / 6 이므로 최고 차항의 차수는 3이다.

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

 

정답 코드

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