πŸ“– Algorithm/πŸ“ λ°±μ€€

Kotlin 🍬 λ°±μ€€ 11단계 :: 24314 번

λ²ŒκΏ€μ˜€μ†Œλ¦¬πŸ¦‘ 2023. 6. 6. 03:35
λ°˜μ‘ν˜•

μ•Œκ³ λ¦¬μ¦˜ μˆ˜μ—… - 점근적 ν‘œκΈ° 2

문제   |

  μ˜€λŠ˜λ„ μ„œμ€€μ΄λŠ” 점근적 ν‘œκΈ° μˆ˜μ—… 쑰ꡐλ₯Ό ν•˜κ³  μžˆλ‹€. μ•„λΉ κ°€ μˆ˜μ—…ν•œ λ‚΄μš©μ„ 학생듀이 잘 μ΄ν•΄ν–ˆλŠ”μ§€ 문제λ₯Ό ν†΅ν•΄μ„œ ν™•μΈν•΄λ³΄μž.

  μ•Œκ³ λ¦¬μ¦˜μ˜ μ†Œμš” μ‹œκ°„μ„ λ‚˜νƒ€λ‚΄λŠ” Ξ©-ν‘œκΈ°λ²•(λΉ…-μ˜€λ©”κ°€)을 λ‹€μŒκ³Ό 같이 μ •μ˜ν•œλ‹€.

  Ξ©(g(n)) = {f(n) | λͺ¨λ“  n ≥ $n_{0}$에 λŒ€ν•˜μ—¬ c × g(n) ≤ f(n)인 μ–‘μ˜ μƒμˆ˜ c와 $n_{0}$κ°€ μ‘΄μž¬ν•œλ‹€}

  이 μ •μ˜λŠ” μ‹€μ œ Ξ©-ν‘œκΈ°λ²•(https://en.wikipedia.org/wiki/Big_O_notation)κ³Ό λ‹€λ₯Ό 수 μžˆλ‹€.

  ν•¨μˆ˜ f(n) = $a_{1}n$ + $a_{0}$, μ–‘μ˜ μ •μˆ˜ c, $n_{0}$κ°€ μ£Όμ–΄μ§ˆ 경우 Ξ©(n) μ •μ˜λ₯Ό λ§Œμ‘±ν•˜λŠ”μ§€ μ•Œμ•„λ³΄μž.

 

μž…λ ₯   |

  μ²«μ§Έ 쀄에 ν•¨μˆ˜ f(n)을 λ‚˜νƒ€λ‚΄λŠ” μ •μˆ˜ $a_{1}$, $a_{0}$κ°€ 주어진닀. (0 ≤ |$a_{i}$| ≤ 100)

  λ‹€μŒ μ€„에 μ–‘μ˜ μ •μˆ˜ cκ°€ 주어진닀. (1 ≤ c ≤ 100)

  λ‹€μŒ μ€„에 μ–‘μ˜ μ •μˆ˜ $n_{0}$κ°€ 주어진닀. (1 ≤ $n_{0}$ ≤ 100)

 

좜λ ₯   |

  f(n), c, $n_{0}$κ°€ Ξ©(n) μ •μ˜λ₯Ό λ§Œμ‘±ν•˜λ©΄ 1, μ•„λ‹ˆλ©΄ 0을 좜λ ₯ν•œλ‹€.

 

 

풀이  |

  O-ν‘œκΈ°λ²• (λΉ…-였)의 λ°˜λŒ€ κ°œλ…

 

 

λ‹΅μ•ˆ  |

import java.util.Scanner

fun main() = with(Scanner(System.`in`)) {
    val a1 = nextInt()
    val a0 = nextInt()
    val c = nextInt()
    val n0 = nextInt()
    
    if ((c * n0 <= a1 * n0 + a0) && (a1 <= c)) {
        print(1)
    } else {
        print(0)
    }
}
λ°˜μ‘ν˜•