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

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

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

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

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

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

제약사항

• 0 < n <= 500,000

주의 사항

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

CPP풀이

알고리즘 수업 - 알고리즘의 수행 시간 5_24266.cpp

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


#include <iostream>

using namespace std;

int main(void)
{
    long long int n;
    cin >> n;
    cout << n * n * n << '\n' << 3 << endl;
    return 0;
}

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

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

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