백준 - 24313번 알고리즘 수업 : 점근적 표기1(수학, 구현)

문제

오늘도 서준이는 점근적 표기 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

알고리즘의 소요 시간을 나타내는 O-표기법(빅-오)을 다음과 같이 정의하자.
O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다}

이 정의는 실제 O-표기법(https://en.wikipedia.org/wiki/Big_O_notation)과 다를 수 있다.

함수 f(n) = a1n + a0, 양의 정수 c, n0가 주어질 경우 O(n) 정의를 만족하는지 알아보자.

입력

첫째 줄에 함수 f(n)을 나타내는 정수 a1, a0가 주어진다. (0 ≤ |ai| ≤ 100)
다음 줄에 양의 정수 c가 주어진다. (1 ≤ c ≤ 100)
다음 줄에 양의 정수 n0가 주어진다. (1 ≤ n0 ≤ 100)

출력

f(n), c, n0가 O(n) 정의를 만족하면 1, 아니면 0을 출력한다.

C++ 풀이

문제 자체는 복잡하지 않은 듯 보였으나 MECE( Mutually Exclusive, Collectively Exhaustive) 하게 조건을 설정하는 데 시행착오가 있었던 문제.

#include <iostream>
using namespace std;
int main(){
    int a1,a0,c,n0;
    cin>>a1>>a0>>c>>n0;
    /* 상한선인 c의 크기 a1보다 큰 경우
    n0가 크로스되는 지점을 기준으로 나뉠 수 있다.
    */
    if (c>a1) {
        if ((c-a1)*n0 >= a0) {
            cout << 1;
        }
        else
            cout << 0;
    }
    /* 상한선인 c의 크기 a1보다 작은 경우
    n0의 값과 무관하게 모든 경우에서 불가능하다.
    */
    else if (c<a1) {
        cout << 0;
    }
    /* 상한선인 c의 크기 a1와 같은 경우
    절편인 a0의 크기가 0보다 작거나 같으면 항상 만족하고, 
    그 외 케이스는 항상 a1의 선이 위에 있으므로 불가능하다.
    */
    else {
        if (a0<=0)
            cout << 1;
        else
            cout << 0;
    }
}