[BOJ 24267] 알고리즘 수업 - 알고리즘의 수행 시간 6 - [수학, 구현]

[BOJ 24267] 알고리즘 수업 - 알고리즘의 수행 시간 6 - [수학, 구현]

문제 링크

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

문제 요약

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

• 입력 크기 $n$ ($1 \le n \le 500,000$)

접근 방법

• 자료구조: 정수형 변수 (long long)
• 알고리즘: 수학 (조합론, Combination)
• 핵심 아이디어:
  • 코드의 3중 반복문 조건($1 \le i < j < k \le n$)을 보면, $1$부터 $n$까지의 수 중에서 서로 다른 3개의 수를 뽑는 경우의 수와 동일함을 알 수 있습니다.
  • 즉, 수행 횟수는 ${}_nC_3 = \frac{n(n-1)(n-2)}{6}$ 입니다.
  • 다항식 $\frac{n(n-1)(n-2)}{6}$은 $n^3$ 항을 가지므로 최고차항의 차수는 3입니다.

풀이 코드

#include <iostream>

using namespace std;

int main() {
    // 입출력 속도 향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n;
    cin >> n;

    // 수행 횟수 계산: nC3
    // n의 범위가 최대 500,000이므로 결과값은 약 2*10^16이 될 수 있음.
    // 따라서 int(약 21억) 범위를 넘어가므로 long long 사용 필수.
    long long count = n * (n - 1) * (n - 2) / 6;

    cout << count << "\n";
    cout << 3 << "\n"; // 알고리즘은 O(n^3)이므로 차수는 항상 3

    return 0;
}

시간/공간 복잡도

• 시간 복잡도: O(1)
  • 입력값 $n$에 대해 공식을 한 번 계산하여 출력하므로 상수 시간이 소요됩니다.
• 공간 복잡도: O(1)
  • 별도의 배열이나 자료구조 없이 변수 하나만 사용합니다.

실행 결과

• 메모리: 2020 KB
• 시간: 0 ms

핵심 포인트

1. 조합 공식 유도: 3중 for문의 i < j < k 조건이 ${}_nC_3$과 같다는 것을 파악해야 합니다.
2. 자료형 선택: $n=500,000$일 때 결과값이 int 범위를 초과하므로 반드시 long long을 사용해야 오버플로우를 방지할 수 있습니다.
3. 상수 출력: 문제 조건에서 차수는 변하지 않으므로 항상 3을 출력합니다.

예제 확인

• 예제 1:
  • 입력: 7
  • 계산: $\frac{7 \times 6 \times 5}{6} = 35$
  • 출력:
  • 35 3