BOJ (C/C++) 24313번: 알고리즘 수업 - 점근적 표기 1

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

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

 

---

풀이

주어진 문제는 a1*n+a0 >= c*n 이므로 이를 정리하면 (c-a1)*n >= a0가 된다. 이 때 a0, a1은 음수가 될 수 있다.

 

1. c-a1>0일 때 : (c-a1)*n >= a0 를 만족하면 O(n)의 정의를 만족한다.

2. c-a1<0일 때

 - a0 >= 0 : (음수) >= (양수)의 형태가 되므로 어느 경우에도 만족하지 못한다.

 - a0 < 0   :  (음수) >= (음수)이므로 이는 (양수) <= (양수)로 바꿀 수 있다. 이 때 좌변은 값이 계속 증가하므로 이 경우에도 O(n)은 만족하지 않는다.

 >> 따라서 2일 때는 어느 경우에도 O(n)을 만족하지 못한다.

3. c-a1 = 0일 때 : 0 >= a0 이므로 a0 = 0인 경우 만족한다.

---

코드

#include <stdio.h>

int main() {
	int a1, a0, c, n0, p = 0;
	scanf("%d %d\n%d\n%d", &a1, &a0, &c, &n0);

	if (c - a1 > 0) {
		if ((c - a1)*n0 >= a0) p = 1;
	}
	else if (c - a1 == 0 && a0 <= 0) p = 1;

	printf("%d", p);
	return 0;
}