(24313) 알고리즘 수업 - 점근적 표기 1

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

단계별로 풀어보기

11단계(시간 복잡도) 7번째

 

 

 

본문 내용을 요약하면, n≥n₀일 때 a₁n+a₀≤cn을 항상 만족하는지를 구하는 문제이다.

이 부등식은 일차식이므로 a₀≤(c-a₁)n가 n=n₀일 때 성립하고 c-a₁≥0를 만족하는 것과 동치이다.

 

 

 

#include <iostream>
using namespace std;

int main() 
{
  int a1, a0, c, n0;
  
  cin >> a1 >> a0 >> c >> n0;
  
  cout << (c-a1>=0 && a0<=(c-a1)*n0);
  
  return 0;
}