[백준/BOJ] 24267번 알고리즘 수업 - 알고리즘의 수행 시간 6 (C/C++)

백준 온라인 저지(BOJ) 24267번 알고리즘 수업 - 알고리즘의 수행 시간 6
https://www.acmicpc.net/problem/24267

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

* 사용언어 : C언어, C++

 

1. 문제

n 이 주어질 때, 아래 알고리즘의 ① 수행 횟수, ②최고차항의 차수를 출력

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

 

2. 풀이

시간 복잡도에 대한 이해,
그리고 시그마 합에 대한 이해가 필요한 문제입니다.
 
주어진 코드는 n 의 크기에 따라 i = 1부터 n - 2까지,
그리고 그 안에서 j = i + 1부터 n - 1까지,
다시 그 안에서 k = j + 1부터 n까지 반복하면서
A[i] * A[j] * A[k] 의 합을 구하여 출력하는 코드 입니다.
 
정확한 수행 횟수 계산을 위해 시그마 합 공식을 활용하여 공식을 구했습니다.

먼저 손으로 풀고 일부만 옮겨 적었기 때문에 수식에 생략이 많습니다.

 

위 공식에 따라 수행 횟수는 (n - 2) * (n - 1) * n / 6이고, 시간 복잡도는 O(n^3)입니다.
 

여기서 최대 n 은 500,000 이므로 최대 출력은 20,833,208,333,500,000 이 되어
int 범위를 넘어갑니다. (int 범위는 대략 21억에서 -21억)
 
그렇기 때문에 n 을 long long 으로 처리를 해주어야 정답이 됩니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
24267_알고리즘 수업 - 알고리즘의 수행 시간 6
1112KB	0ms
*/
#include <cstdio>

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	long long int n;
	scanf("%lld", &n);
	
	printf("%lld\n3\n", (n - 2) * (n - 1) * n / 6);
	return 0;
}