백준-시간복잡도 24267 알고리즘 수업 - 알고리즘의 수행 시간 6

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

반복문 중첩을 통해 모든 항을 곱한뒤 더하는 프로그램

수식은 an ** 3 + bn ** 2 + cn + d이므로 최고차항의 계수는 3, 수행 시간은 n**3 +@만큼 반복한다.

문제를 풀면서 알게 되겟지만 반복문이 중첩될 수록, 같은 입력이 주어지더라도 수행 횟수가 기하급수적으로 늘어난다.

이번 문제는 수행 시간의 제한이 있기 때문에 단순히 3중첩 반복문으로 출력해서는 안된다. 

 

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

제약사항

• 0 < n <= 500,000

주의 사항

최고 입력 횟수가 50만번 이므로 최대 연산 횟수는 20억번이 넘어가기 때문에 자료형이 바뀌어야 한다.

CPP풀이

알고리즘 수업 - 알고리즘의 수행 시간 6_24267.cpp

/**
 * 백준 알고리즘 수업 - 알고리즘의 수행 시간 6_24267
 * 반복문 중첩을 통해 모든 항을 곱한뒤 더하는 프로그램
 * 수식은 an ** 3 + bn ** 2 + cn + d이므로 최고차항의 계수는 3, 수행 시간은 n**3 +@만큼 반복한다.
 * 문제를 풀면서 알게 되겟지만 반복문이 중첩될 수록, 같은 입력이 주어지더라도 수행 횟수가 기하급수적으로 늘어난다.
 * n * (n - 1) * (n - 2) / 6
 * 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;
 * }
 * 
 * 제한사항
 *****************************************
 * 0 < n <= 500,000                      *
 *****************************************
 *
 *
 *
 * 주의
 * 최고 입력 횟수가 50만번 이므로 최대 연산 횟수는 20억번이 넘어가기 때문에 자료형이 바뀌어야 한다.
 * 
 * 풀이시간 5분
 */


 #include <iostream>

 using namespace std;
 
 int main(void)
 {
     long long int n, sum = 0;
     cin >> n;

     cout << n * (n - 1) * (n - 2) / 6 << '\n' << 3 << endl;
     return 0;
 }

모든 예제 코드의 소스파일은 제 개인 깃허브 레포지토리 에 있습니다.

Workspace/알고리듬 풀이 at main · cyphen156/Workspace · GitHub

Workspace/알고리듬 풀이 at main · cyphen156/Workspace