(매일 BOJ) C++ 24265번 알고리즘 수업 - 알고리즘의 수행 시간 4

이번 문제는 24265번 알고리즘 수업 - 알고리즘의 수행 시간 4 이다.

접근법

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

 

이 문제의 MenOfPassion 함수에서는 이중 for 문을 사용하여 작동하고 있는데, j의 값이 i가 증가함에 따라 같이 증가하여 점화식을 세우면 sigma N-1 이 되는 것을 볼 수 있다. 따라서 for 문을 이용하여 하나씩 값을 더한 후 첫째 줄을 출력하면 되고, 둘째 줄은 이 문제의 시간복잡도도 N을 무한대로 근사시킨다면 O(N^2) 에 근사하기에 2를 출력하면 된다.

 

시간복잡도에 대해 더 알아보고 싶으면 아래 글을 읽어보자

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/

[알고리즘] Time Complexity (시간 복잡도) - 하나몬

 

작성코드

# include <bits/stdc++.h>
using namespace std;


int main(void){
    ios::sync_with_stdio(0); cin.tie(0);
    long long N;
    cin >> N;
    long long sum = 0;
    for (int i  = 1; i < N; i++){
        sum += i;
    }
    cout << sum << '\n' << 2;
}