[Swift 코테] 백준 24313 알고리즘 수업 - 점근적 표기 1

---

• f(n) = a1 * n + a0
• g(n) = n
• 모든 n >= n0에 대해 f(n) <= c* g(n)이 성립해야 한다.
  1. 모든 n >= n0에 대해
  2. f(n) <= c * g(n)이 성립

 

다음과 같은 과정으로 n의 범위를 정리할 수 있고 1번이 성립하기 위해서는 n0보다 n의 범위가 작아야 한다.

백준 예제로 예를 들자면 f(n) = 7n + 7, g(n) = n, c = 8, n0 = 10이다. 모든 n ≥ 10에 대하여 7n + 7 ≤ 8n 이므로 O(n) 정의를 만족한다.

=> 7 ≤ n 일 때 모든 10 < n 이 성립한다.

• 2번 조건에서 n이 7보다 크거나 같으면 f(n) <= c * g(n)이 성립하는데
• 1번 조건의 n은 10(n0)보다 크기 때문에 2번 조건의 범위에 포함되어서 O(n)의 정의를 만족한다.
• 또한 c-a1이 분모자리에 위치해서 0이 되면 안 되는 범위 내에서 구해야 런타임에러가 발생하지 않는다.

 

 

 

// 24313 알고리즘 수업 - 점근적 표기 1 코드

let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (a1, a0) = (input[0], input[1])
let c = Int(readLine()!)!
let n = Int(readLine()!)!

var result = 1
if c - a1 != 0 {
    if (a0/(c-a1)) <= n {
        result = 1
    }else{
        result = 0
    }
}

if a1 * n + a0 > c * n {
    result = 0
}

print(result)