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

📔문제

오늘도 서준이는 점근적 표기 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

알고리즘의 소요 시간을 나타내는 O-표기법(빅-오)을 다음과 같이 정의하자.

O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다}

이 정의는 실제 O-표기법(https://en.wikipedia.org/wiki/Big_O_notation)과 다를 수 있다.

함수 f(n) = a1n + a0, 양의 정수 c, n0가 주어질 경우 O(n) 정의를 만족하는지 알아보자.

---

📝입력

첫째 줄에 함수 f(n)을 나타내는 정수 a1, a0가 주어진다.
(0 ≤ |ai| ≤ 100)
다음 줄에 양의 정수 c가 주어진다. (1 ≤ c ≤ 100)
다음 줄에 양의 정수 n0가 주어진다. (1 ≤ n0 ≤ 100)

---

📺출력

f(n), c, n0가 O(n) 정의를 만족하면 1, 아니면 0을 출력한다.

---

📝예제 입력 1

7 7
8
1

---

📺예제 출력 1

0

f(n) = 7n + 7, g(n) = n, c = 8, n0 = 1이다. f(1) = 14, c × g(1) = 8이므로 O(n) 정의를 만족하지 못한다.

---

📝예제 입력 2

7 7
8
10

---

📺예제 출력 2

1

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

---

🔍출처

-문제를 검수한 사람: heeda0528, jhnah917, jthis, tlsdydaud1
-문제를 만든 사람: MenOfPassion

---

🧮알고리즘 분류

• 수학
• 구현
• 시뮬레이션

---

📃소스 코드

import java.util.Scanner;

public class Code24313 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner=new Scanner(System.in);
		
		int a1=scanner.nextInt();
		int a0=scanner.nextInt();
		int c=scanner.nextInt();
		int n0=scanner.nextInt();
		
		double value=0;
		
		if(a1==c) {
			if(a0==0) {
				System.out.println(1);
			}
			else if(a0<0){
				System.out.println(1);
			}
			else {
				System.out.println(0);
			}
		}
		else if(a1==0) { //ex) 7<=8n  n>=7/8
			if(a0==0) { //ex) 0<=7n , 0<=n
				System.out.println(1);
			}
			else if(a0<0) {
				System.out.println(1);
			}
			else {
				value=a0/c;
				getValue(n0, value);
			}
		}
		else {
			if(a1>c){//ex)10n+7<=8n 2n<=-7  n<=-7
				if(a0==0) {
					System.out.println(0);
				}
				else if(a0<0) {
					if(n0<=value) {
						System.out.println(1);
					}
					else {
						System.out.println(0);
					}
				}
				else {
					System.out.println(0);
				}
				
			}
			else if(a1<c){//ex)7n+7<=8n n>=7
				if(a0==0) {
					System.out.println(1);
				}
				else if(a0<0) {
					System.out.println(1);
				}
				else {
					value=a0/(c-a1);
					getValue(n0, value);
					
				}
			}
		}
		
	}

	public static void getValue(int n0, double value) {
		if(n0>=value) {
			System.out.println(1);
		}
		else {
			System.out.println(0);
		}
	}

}

---

📰출력 결과

---

📂고찰

엉엉엉 조건을 잘못봤다.
음수는 없을거라 생각했는데 절댓값이었다.

1. a1==c
만약 a0가 0이면 항상 참, //8n<=8n
a0이 음수면 항상 참,//8n-7<=8n
그렇지 않으면 항상 거짓 //8n+7<=8n

2. a1==0
만약 a0도 0이면 항상 참,//0<=7n
a0이 음수면 항상 참,//-7<=7n
그렇지 않으면 n0의 값이 value값보다 크거나 같아야한다.//7<=7n, 1<=n

3. a1>c
만약 a0이 0이면 항상 거짓,//7n<=6n
a0이 음수면 n0은 a0보다 value보다 작거나 같아야 한다.//7n-3<=6n n<=3
그렇지 않으면 항상 거짓 //7n+5<=6n n<=-5

4. a1<c
만약 a0이 0이면 항상 참, //7n<=8n
a0이 음수면 항상 참//7n-7<=9n -7/9<=n
그렇지 않으면 n0의 값이 value의 값보다 크거나 같아야한다.//7n+7<=9n 7/9<=n