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

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

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

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

 

1. 문제

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

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

 

2. 풀이

시간 복잡도에 대한 이해가 필요한 문제입니다.
 
주어진 코드는 n 의 크기에 따라 1부터 n 까지 n 회(i),
그리고 그 안에서 다시 1부터 n 까지 n 회(j),
다시 그 안에서 다시 1부터 n 까지 n회(k) 반복하면서
A[i] * A[j] * A[k] 의 합을 구하여 출력하는 코드 입니다.
 
따라서 시간 복잡도는 O(n^3) 이 되고, 출력은 n^3 과 3이 됩니다.
 
여기서 최대 n 은 500,000 이므로 n^3 은 125,000,000,000,000,000 이 되어
int 범위를 넘어갑니다. (int 범위는 대략 21억에서 -21억)
 
그렇기 때문에 n 을 long long 으로 처리를 해주어야 정답이 됩니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
24266_알고리즘 수업 - 알고리즘의 수행 시간 5
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 * n * n);
	return 0;
}