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

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

문제 링크

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

문제 요약

주어진 MenOfPassion 알고리즘(이중 for문 구조)의 수행 횟수와 시간 복잡도의 차수(최고차항)를 출력하는 문제.

• 입력 크기 $n$ ($1 \le n \le 500,000$)에 대해 코드의 핵심 루프가 실행되는 총횟수를 구해야 함.

접근 방법

• 자료구조: 정수형 변수 (long long)
• 알고리즘: 수학 (등차수열의 합)
• 핵심 아이디어:
  • 외부 루프 i는 $1$부터 $n-1$까지 반복하고, 내부 루프 j는 $i+1$부터 $n$까지 반복합니다.
  • i에 따른 수행 횟수는 다음과 같습니다:
    • $i=1$: $n-1$회
    • $i=2$: $n-2$회
    • ...
    • $i=n-1$: $1$회
  • 따라서 전체 수행 횟수는 $1$부터 $n-1$까지의 합이며, 등차수열의 합 공식인 $\frac{n(n-1)}{2}$로 계산됩니다.

풀이 코드

#include <iostream>

using namespace std;

int main() {
    // 입출력 속도 향상 (C++ 표준 입출력과 C 입출력 혼용 방지 및 버퍼 관리)
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n; // n의 최대값이 500,000이므로 n^2 계산 시 int 범위를 초과할 수 있음
    cin >> n;

    // 1. 수행 횟수 출력: n * (n-1) / 2
    // 계산 결과가 21억을 넘을 수 있으므로 long long 연산 필요
    cout << (n * (n - 1)) / 2 << "\n";

    // 2. 최고차항의 차수 출력
    // 수행 횟수 식은 (n^2 - n) / 2 이므로, n에 대한 최고차항은 n^2.
    // 따라서 차수는 항상 2이다.
    cout << 2 << "\n";

    return 0;
}

시간/공간 복잡도

• 시간 복잡도: $O(1)$ (반복문을 사용하지 않고 수식으로 즉시 계산)
• 공간 복잡도: $O(1)$ (입력값을 저장할 변수 하나만 사용)

실행 결과

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

핵심 포인트

1. 자료형 선택 (long long): 입력 $n$이 최대 $500,000$일 때, 수행 횟수는 약 $\frac{25 \times 10^{10}}{2} \approx 1.25 \times 10^{11}$이 됩니다. 이는 int형의 최대 범위(약 $2 \times 10^9$)를 초과하므로 반드시 long long을 사용해야 오버플로우를 방지할 수 있습니다.
2. 수학적 접근: $N$이 커질 경우 이중 루프를 직접 시뮬레이션하면 시간 초과($O(N^2)$)가 발생할 수 있습니다. 문제의 의도에 맞춰 수학적 공식으로 $O(1)$에 해결해야 합니다.

예제 확인

• 예제 1:
  • 입력: 7
  • 수행 횟수: $1 + 2 + 3 + 4 + 5 + 6 = 21$ (또는 $\frac{7 \times 6}{2} = 21$)
  • 차수: $2$
  • 출력:
  • 21 2