백준 24313번 알고리즘 수업 - 점근적 표기 1 [C++]

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

24313번: 알고리즘 수업 - 점근적 표기 1

 

 

주어진 입력에 따라, 문제에 나온 공식이 참이 되면 1을, 거짓이 되면 0을 출력하는 문제이다.

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int a1, a0, c, n0;
    cin >> a1 >> a0 >> c >> n0;
   
    int fn = a1*n0 + a0;
    int cgn = c * n0;

    if (fn <= cgn && a1 <= c)
        cout << 1;
    else   
        cout << 0;

}

 

맨 처음에는 g(n) = n 이라는 게 도대체 어디 나와있나 이해하지 못했었다.

다른 글을 찾아보니, O-표기법을 O(g(n))으로 정의했기 때문에, g(n) = n 이 성립하게 된다고 한다.

그래서, 간단하게 a1 * n0 + a0 <= c * g(n0) 으로 조건문을 작성했지만 통과하지 못했다.

 

이유를 찾아보니, a1과 a0의 입력이 꼭 양수로만 들어오는 것이 아님이 문제에 제시되어 있는데, a1이 음수로 들어오는 경우는 어차피 c * g(n) 쪽이 항상 더 크기 때문에 신경 쓸 필요는 없지만, 문제는 a0이 음수로 들어오는 경우이다.

 

예를 들어, a1 = 5, a0 = - 5, c = 4, n0 = 3 라고 하자.

그러면 처음에는 a1 * n0 + a0 = 10, c * n0  = 12 가 되므로 문제의 식이 참이 되지만, 문제에서 모든 n >= n0 에서 만족해야 한다고 했으므로, n3 = 6, a1 * n3 + a0 = 25, c * n3 = 24 가 되므로 문제의 식이 거짓이 되버린다.

즉, 처음에는 참이라고 판단했지만, n이 증가하면서 어느 시점부터 거짓이 되므로 모든 n >= n0에서 만족해야 한다는 조건을 만족시키지 못하는 것이다.

 

이를 해결하려면 a1 <= c 라는 조건을 넣으면 된다.

어떻게 이 조건이 나오냐면,

a1 * n0 + a0 <= c * n0

a0 <= (c - a1)n0

이므로, 이를 만족시키기 위해 a1 <= c 라는 조건을 넣는 것이다.