[백준] 24267번: 알고리즘 수업 - 알고리즘의 수행 시간 6 | C++ 풀이

# 문제

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

MenOfPassion 알고리즘은 다음과 같다.

 

 

---

 

# 풀이

시간복잡도 여섯 번째 단계!

문제에서 제시한 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;
}

이번에는 3중 for문인데 인덱스가 좀 다르다.

 

 

예제 입력의 n = 7인 경우를 살펴보면 인덱스 진행은 위 표와 같다.

이는 (5 + 4 + 3 + 2 + 1 ) + (4+ 3 + 2 + 1) + (3 + 2 + 1) + (2 + 1) + 1번인데 시그마 공식을 활용해보면 아래와 같다.

 

$$  \sum_{i=1}^{n-2}\sum_{j=1}^{i}j = \frac{(n-2) (n-1) n}{6} $$ 

따라서 어떤 n을 넣더라도 코드 1은 (n-2)(n-1)n/6회 수행, 수행 시간은 n³에 비례함을 알 수 있다.

시간 복잡도는 지난 번과 마찬가지로 O(n³)이고, 항상 (n-2)(n-1)n/6와 3를 개행하여 출력해주면 끝!

 

 

 

#include <iostream>
using namespace std;

int main(){
    long long n;
    cin >> n;
    cout << (n-2)*(n-1)*n/6 << '\n' << 3;
    return 0;
}

이번에도 n의 곱셈연산이 포함되기 때문에 자료형은 long long으로 설정해주었다.

시그마 계산만 잘 해줬다면 코드 짜는 것은 어렵지 않았을 거다!

 

알고리즘 수행시간 6문제 끝! 더보기를 눌러 알고리즘 수행시간 풀이 모아보기~

[백준] 24262번: 알고리즘 수업 - 알고리즘의 수행 시간 1 | C++ 풀이

 

[백준] 24263번: 알고리즘 수업 - 알고리즘의 수행 시간 2 | C++ 풀이

 

[백준] 24264번: 알고리즘 수업 - 알고리즘의 수행 시간 3 | C++ 풀이

 

[백준] 24265번: 알고리즘 수업 - 알고리즘의 수행 시간 4 | C++ 풀이

 

[백준] 24266번: 알고리즘 수업 - 알고리즘의 수행 시간 5 | C++ 풀이

 

 

 

---

 

 

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