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

문제

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

알고리즘의 소요 시간을 나타내는 O-표기법(빅-오)을 다음과 같이 정의하자.

 

$O(g(n)) = \{ f(n)\text{ | 모든 } n ≥ n_0 \text{에 대하여 } f(n) ≤ c × g(n) \text{인 양의 상수 } c \text{와 } n_0 \text{가 존재한다.} \}$

 

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

함수 $f(n) = a_{1}n + a_{0}$, 양의 정수 c, n_{0}가 주어질 경우$O(n)$ 정의를 만족하는지 알아보자.

 

입력

첫째 줄에 함수 f(n)을 나타내는 정수 $a_1, a_0$가 주어진다. ($0 ≤ |a_{i}| ≤ 100$)

다음 줄에 양의 정수 c가 주어진다. ($1 ≤ c ≤ 100$)

다음 줄에 양의 정수 n0가 주어진다. ($1 ≤ n_0 ≤ 100$)

 

출력

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

 

예제 입력 1 

7 7
8
1

 

예제 출력 1 

0

$f(n) = 7n + 7,\; g(n) = n,\; c = 8,\; n_0 = 1$이다. $f(1) = 14,\; c × g(1) = 8$이므로 $O(n)$ 정의를 만족하지 못한다.

 

예제 입력 2 

7 7
8
10

 

예제 출력 2 

1

$f(n) = 7n + 7,\; g(n) = n,\; c = 8,\; n_0 = 10$이다. 모든 $n ≥ 10$에 대하여 $7n + 7 ≤ 8n$ 이므로 $O(n)$ 정의를 만족한다.

 

알고리즘 분류

• 수학

 

문제 출처

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

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

 

---

 

문제 해결 방법

• 문제에서 주어진 조건은 다음과 같다.

$$O(g(n)) = \{ f(n)\text{ | 모든 } n ≥ n_0 \text{에 대하여 } f(n) ≤ c × g(n) \text{인 양의 상수 } c \text{와 } n_0 \text{가 존재한다.} \}$$

 

• 문제에서 $f(n) = a_{1}n + a_{0}$이고, $c, \; n_{0} ≥ 0$이라는 조건이 주어졌다.
• 문제에서 $g(n) = n$이라고 제시되었기 때문에 $g(n) = n$이다.
• 입력값은 $a_{1}, \; a_{0}, \; c, \; n_{0}$이다.
• 이를 토대로 정리해보면 다음과 같다.

$$a_{1}n + a_{0} ≤ cn \quad (n ≥ n_{0})$$

 

• 따라서 위의 조건을 만족시킬 경우, 1을, 그렇지 않을 경우 0을 출력시키면 된다. 코드로 작성해보면 다음과 같다.

			
			
			
		
if (a1 * n + a0 <= c * n) {
   return true;
}

 

• 하지만, $a_{0}$가 음수인 경우도 생각해주어야 한다.
• 예를 들어, $5n - 3 ≤ 3n$이고, $n_{0} = 1$일 경우
  • $n = 1$일 때 만족한다. ($2 ≤ 3$)
  • 하지만 $n = 2$일 때 만족하지 않는다. ($7 ≤ 6$)
• 따라서, $a_{1} ≤ c$ 라는 조건을 추가적으로 추가해주어야 한다. 

			
			
			
		
if (a1 * n + a0 <= c * n) {
    if (a1 <= c) {
        return true;
    }
    else {
        return false;
    }
}
else {
    return false;
}

 

코드

			
			
			
		
#include <iostream>
using namespace std;
 
int a1, a0, c, n0;
 
void Input() {
    cin >> a1 >> a0 >> c >> n0;
}
 
bool Solution(int a1, int a0, int c, int n) {
    if (a1 * n + a0 <= c * n) {
        if (a1 <= c) {
            return true;
        }
        else {
            return false;
        }
    }
    else {
        return false;
    }
}
 
void Output() {
    cout << Solution(a1, a0, c, n0) << '\n';
}
 
void Solve() {
    Input();
    Output();
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    Solve();
 
    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [시간 복잡도]
• 실버V