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

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

24265번: 알고리즘 수업 - 알고리즘의 수행 시간 4

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

 

1. 문제

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

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

 

2. 풀이

시간 복잡도에 대한 이해가 필요한 문제입니다.
 
주어진 코드는 n 의 크기에 따라 1부터 n - 1 까지 n - 1회(i),
그리고 그 안에서 다시 i + 1부터 n 까지 n - i - 1회(j) 반복하면서
A[i] * A[j] 의 합을 구하여 출력하는 코드 입니다.
 
j 가 i 의 값에 따라 달라지기 때문에
정확한 수행 횟수 계산을 위해 i = 1부터 생각해보았습니다.
 
i = 1 인 경우, j 는 2 부터 n 까지 총 n - 1회 입니다.
i = 2 인 경우, j 는 3 부터 n 까지 총 n - 2회 입니다.
...
i = n - 2 인 경우, j 는 n - 1 부터 n 까지 총 2회 입니다.
i = n - 1 인 경우, j 는 n 부터 n 까지 총 1회 입니다.
 
위에서 구한 j 의 반복 횟수를 거꾸로 더해보면,
총 수행 횟수는 1 + 2 + ... + (n - 2) + (n - 1) 이므로
결국 (n - 1) * n / 2 이라고 할 수 있습니다.
 
따라서 시간 복잡도는 O(n^2) 이 되고, 출력은 (n - 1) * n / 2 와 2 가 됩니다.
수식으로는 아래와 같이 증명할 수 있습니다.

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

 

3. 코드

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