[백준] 24267 - 시간복잡도, 식 유도 및 설명

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

24267번: 알고리즘 수업 - 알고리즘의 수행 시간 6 (acmicpc.net)

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

 

1. 소스코드 🧑‍💻

#include <iostream>

using namespace std;


int main()
{
    long long num;
    cin >> num;

    long long many = 0;
    int power=3;

    many = (num - 2) * (num - 1) * num / 6;

    cout << many << endl;
    cout << power;

    return 0;
}

---

2. 유도 과정 및 설명 🧑‍🏫

a) many = (num - 2) * (num - 1) * num / 6; - 의 과정

유도과정

 

+ (질문 답변🙋) 어떻게 첫 번째 식(n-j)에서 두 번째 식(n-i)(n-i-1)/2으로 전개 되나요?

=> 등차수열의 합으로 전개된 것 입니다. 연속된 정수들은 +1씩 증가하기 때문에 등차수열로 볼 수 있습니다.

평균을 통해 함수의 적분을 구하는 것과 비슷한 느낌 -  미적분학 - 함수의 평균 — Everyday Image Processing (tistory.com)

 

아래 식을 직관적으로 이해하자면, (나열된 숫자의 개수)*(숫자들의 평균)이라 생각하시면 됩니다.

(나열된 숫자의 개수): i+1 에서 n-1까지의 정수 개수 = n - i - 1

(숫자들의 평균): (수열의 첫 원소 + 수열의 마지막 원소) / 2 = (n - i) / 2 

=> (나열된 숫자의 개수)*(숫자들의 평균) = ( n - i - 1) * { (n - i) / 2 }

 

출처: blog.naver.com/biomath2k/221832907622

---

3. 배운 것 & 유의 지점 💀

수학적인 문제로 부딪혔다. 시그마 합 공식은 다음과 같다:

a) 시그마 합 공식

수능 끝나고 나서 다 까먹었다.

 

b) long long - 자료형의 크기, 범위 유의하기

처음에 many를 int로 썼다가 범위가 초과되어서 문제가 되었다.

n(1 ≤ n ≤ 500,000) 인데, many = (n-2)(n-1)(n)/6 이여서 int의 범위를 넘게 될 수 있다.

 

그러므로 many를 long long으로 바꾸었다.

1byte = 8 bits