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

백준 온라인 저지(BOJ) 24264번 알고리즘 수업 - 알고리즘의 수행 시간 3
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
            sum <- sum + A[i] × A[j]; # 코드1
    return sum;
}

 

2. 풀이

시간 복잡도에 대한 이해가 필요한 문제입니다.

주어진 코드는 n 의 크기에 따라 1부터 n 까지 n 회(i),
그리고 그 안에서 다시 1부터 n 까지 n 회(j) 반복하면서
A[i] * A[j] 의 합을 구하여 출력하는 코드 입니다.

따라서 시간 복잡도는 O(n^2) 이 되고, 출력은 n^2 과 2 가 됩니다.

여기서 최대 n 은 500,000 이므로 n^2 은 250,000,000,000(2,500억) 이 되어
int 범위를 넘어갑니다. (int 범위는 대략 21억에서 -21억)

그렇기 때문에 n 을 long long 으로 처리를 해주어야 정답이 됩니다.

 

3. 코드

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

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