[BOJ 24313] 알고리즘 수업 - 점근적 표기 1 - [수학 / 구현]

[BOJ 24313] 알고리즘 수업 - 점근적 표기 1 - [수학 / 구현]

문제 링크

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

문제 요약

함수 $f(n) = a_1n + a_0$와 양의 정수 $c, n_0$가 주어질 때, 모든 $n \ge n_0$에 대하여 $f(n) \le c \cdot g(n)$ (단, $g(n) = n$)을 만족하는지 판별하는 문제.

접근 방법

• 자료구조: 단순 변수 (int)
• 알고리즘: 수학적 조건 판별
• 핵심 아이디어:
  • 빅오 표기법의 정의를 만족하려면 두 가지 조건을 동시에 충족해야 합니다.
  1. 시작점 조건: $n = n_0$일 때, $f(n_0) \le c \cdot n_0$가 성립해야 합니다.
  2. 기울기 조건: $n$이 $n_0$보다 커질 때 $f(n)$이 $c \cdot n$을 추월하지 않아야 하므로, $f(n)$의 기울기 $a_1$이 $c \cdot n$의 기울기 $c$보다 작거나 같아야 합니다 ($a_1 \le c$).

풀이 코드

#include <iostream>

using namespace std;

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

    int a1, a0, c, n0;
    
    // 입력: a1, a0 (f(n)의 계수), c (상수), n0 (시작값)
    cin >> a1 >> a0 >> c >> n0;

    // f(n0) = a1 * n0 + a0
    // g(n0) = n0
    // 조건 1: a1 * n0 + a0 <= c * n0
    // 조건 2: a1 <= c (n이 무한히 커질 때 f(n)이 c*n을 넘지 않기 위함)
    if ((a1 * n0 + a0 <= c * n0) && (a1 <= c)) {
        cout << 1 << "\n";
    } else {
        cout << 0 << "\n";
    }

    return 0;
}

시간/공간 복잡도

• 시간 복잡도: $O(1)$ - 단순히 몇 개의 산술 연산과 조건문만 수행하므로 입력 크기와 상관없이 일정합니다.
• 공간 복잡도: $O(1)$ - 4개의 정수형 변수만 사용합니다.

실행 결과

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

핵심 포인트

1. 단순히 $n_0$ 대입값만 비교하면 안 됩니다. $a_1 > c$인 경우, 초기값은 작을 수 있으나 $n$이 커짐에 따라 결국 좌변이 더 커지게 되므로 **기울기 비교($a_1 \le c$)**가 필수적입니다.
2. $a_1$과 $a_0$의 범위에 음수가 포함될 수 있으므로(절댓값이 100 이하), $a_1 \le c$ 조건을 빼먹으면 틀릴 확률이 높습니다.

예제 확인

• 예제 1: 7 7, 8, 1 -> $f(1)=14, 8 \cdot 1=8$. $14 \le 8$은 거짓 $\rightarrow$ 0 출력.
• 예제 2: 7 7, 8, 10 -> $f(10)=77, 8 \cdot 10=80$. $77 \le 80$이고 $7 \le 8$이므로 참 $\rightarrow$ 1 출력.