[BOJ 24266] 알고리즘 수업 - 알고리즘의 수행 시간 5 - [수학/구현]

[BOJ 24266] 알고리즘 수업 - 알고리즘의 수행 시간 5 - [수학/구현]

문제 링크

https://www.acmicpc.net/problem/24266

문제 요약

주어진 3중 중첩 반복문 알고리즘(MenOfPassion)의 실행 횟수와 해당 수행 시간을 다항식으로 나타냈을 때의 최고차항 차수를 출력하는 문제입니다.

접근 방법

• 자료구조: 없음 (기본 변수 사용)
• 알고리즘: 수학적 분석 (시간 복잡도 계산)
• 핵심 아이디어: 1. 의사코드에서 $i, j, k$가 각각 $1$부터 $n$까지 순차적으로 반복되므로 전체 수행 횟수는 $n \times n \times n = n^3$입니다. 2. 입력값 $n$이 최대 500,000이므로, $n^3$은 최대 $1.25 \times 10^{17}$이 되어 int 범위를 초과합니다. 따라서 C++에서는 long long 자료형을 사용해야 합니다. 3. $n^3$은 3차식이므로 최고차항의 차수는 항상 3입니다.

풀이 코드

#include <iostream>

using namespace std;

int main() {
    // 입출력 성능 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n;
    // 입력의 크기 n을 입력받음
    if (!(cin >> n)) return 0;

    // 코드1의 수행 횟수 출력 (n^3)
    // n이 500,000일 때 n^3은 약 12.5경이므로 long long 필수
    cout << n * n * n << "\n";

    // 다항식으로 나타냈을 때 최고차항의 차수 출력 (n^3 이므로 3)
    cout << 3 << "\n";

    return 0;
}

시간/공간 복잡도

• 시간 복잡도: $O(1)$ (단순 입출력 및 곱셈 연산만 수행하므로 입력값 $n$과 무관하게 상수 시간 소요)
• 공간 복잡도: $O(1)$ (입력값을 저장하는 하나의 변수 외에 추가 메모리 사용 없음)

실행 결과

• 메모리: 2020 KB (표준 입출력 사용 시 일반적인 결과)
• 시간: 0 ms (상수 시간 연산)

핵심 포인트

1. 오버플로우 방지: $n^3$ 계산 시 int 범위를 넘어서는 큰 값을 처리하기 위해 반드시 long long 타입을 사용해야 합니다.
2. 차수의 고정: 알고리즘이 3중 for문이므로 $n$의 값과 상관없이 차수는 항상 3이 됩니다.

예제 확인

• 예제 1:
  • 입력: 7
  • 계산: $7 \times 7 \times 7 = 343$
  • 출력: 1행에 343, 2행에 3 (예제와 일치)