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

목차

---

백준 단계별로 풀어보기

25.09.30

11단계: 시간 복잡도

24264번: 알고리즘 수업 - 알고리즘의 수행 시간 3

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

 

문제 풀이

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

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

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

• 배열 'A[]' 과 'n' 을 입력받는다.
• 'sum'에 0을 대입한다.
• for 반복문을 이중으로 사용하여 1부터 n까지 반복하며 sum에 A[i] × A[j] 값을 더하고 sum에 대입한다.
• sum을 반환한다.

 

>> 풀이

: 1부터 입력받은 n까지 for 반복문을 이중으로 사용하기 때문에 n² 만큼 코드1을 반복하고 알고리즘이 종료된다. 따라서 코드 1의 수행 횟수는 n² 번 즉, f(n) = n² 이므로 최고 차항의 차수는 2이다.

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

 

정답 코드

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