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

핵심 포인트

• 시간 복잡도

제출코드

a0, a1 = map(int, input().split())
c = int(input())
n0 = int(input())

flag = 1
for i in range(n0, 100):
  if a0 * i + a1 > c * i:
    flag = 0
    break
print(flag)

해설

다항식 $f(n)$의 계수인 $a_{0}$와 $a_{1}$ 그리고 상수 $c$와 $n_{0}$를 먼저 입력받습니다. 이 문제에서 확인해야할 것은 $n \ge n_{0}$에 대한 모든 $n$에 대해서 $f(n) \le c \times n$을 만족하는 지 확인해야합니다. 다만, 저희가 무한대의 수를 검증할 수는 없기 때문에 제한을 두어서 $n_{0}$부터 100까지 숫자에 대해서만 확인합니다. 이때, 해당 부등식을 만족하지 않는 다면 flag를 0으로 바꾼 뒤 출력하면 됩니다. 

 

참고자료 및 그림출처

백준 코딩 문제