백준 알고리즘 24265번 알고리즘 수업 - 알고리즘의 수행 시간 4 (C++/C언어)

브론즈 Ⅲ

 

https://www.acmicpc.net/problem/24265

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

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	2771	1504	1429	55.280%

 

문제

오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.

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

입력

첫째 줄에 입력의 크기 n(1 ≤ n ≤ 500,000)이 주어진다.

출력

첫째 줄에 코드1 의 수행 횟수를 출력한다.

둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.

예제 입력 1

7

예제 출력 1 

21
2

 

풀이 방법

이 문제는 주어진 MenOfPassion 알고리즘 속 코드1(sum <-  sum + A[i] x A[j];)의 수행 횟수와 수행횟수를 다항식으로 나타냈을 때의 최고차항의 차수를 출력하는 문제입니다.

 

MenOfPassion 함수는 배열 A와 정수 n을 인자로 전달받아 2중 for문을 이용해 i의 값은 1부터 n-1까지,  j의 값은 i+1부터 n까지 증가시키며, A의 i번째 인덱스에 있는 값과 A의 j번째 인덱스에 있는 값을 곱해 sum에 모두 더해주고 마지막으로 sum의 값을 return하는 함수입니다.

 

이 함수가 실행될 때 'sum <- sum + A[i] x A[j];'는 입력값 n이 아래와 같을 때 다음과 같은 수행횟수를 가집니다.

1	2	3	4	5	6	7
0	1	1+2 = 3	1+2+3 = 6	1+2+3+4 = 10	1+2+3+4+5=15	1+2+3+4+5+6 = 21

이를 통해 n의 수행횟수는 0부터 n-1까지의 합임을 알 수 있습니다. 따라서 1부터 n까지의 합을 구하는 공식 (n*(n+1)) / 2를 이용하면 1부터 n-1까지의 합은 식 ((n-1)*n) / 2을 이용해 구할 수 있습니다. 또한 수행횟수를 계산해보면 n*(n-1)이 되기 때문에,

이 코드의 시간 복잡도(Time Complexity)를 빅오 표기법(Big-O Notation)으로 나타내면 O(n^2)임을 알 수 있습니다.

 

내 코드

반응형

#include <iostream>
 
using namespace std;
 
int main() {
 
    int n;
    cin >> n; //C언어 : scanf("%d", &n);
 
    cout << (n*(n-1))/2 << '\n' << 2 << endl; //C언어 : printf("%d\n%d\n", (n*(n-1))/2, 2);
 
    return 0;
}

 

코드설명

 

코드1의 수행횟수와 코드1을 다항식으로 나타냈을 때의 최고차항의 차수는 n의 값에 따라 n*(n-1)/2와 2이기 때문에 n을 입력 받고 n*(n-1)/2를 계산한 값과 2 출력하면 됩니다.