백준 24313_<알고리즘 수업 - 점근적 표기 1>

24313번: 알고리즘 수업 - 점근적 표기 1 (acmicpc.net)

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

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

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

이게 전제조건인데 보면 주어진 양수 이상의 모든 구간에 대해 저 조건을 만족하는것을 O()로 정의했다.사실 "여기서 o(N)의 정의를 만족하는지 물어봤기에 G(N)= N인것을 알 수 있고이제는 f(n) ≤ c × g(n)의 대소비교를 하는 코드를 구현하면 끝.

 

sol1.

일차함수의 관점으로 문제 접근했다.

h(n)=cg(n)-f(n)으로 정의하자. 그렇다면 h(n)은 n에 대한 일차식일 것. 주어진 n의 range는 무조건 양수이다.

즉 양수~양의 무한대 의 구간에서 늘 0보다 커야한다.

 

일단 3개의 관점에서 볼수있다.

1. h(n)의 n의 계수가 0보다 클때

 

2. h(n)의 n의 계수가 0일때 - 이땐 상수인 a0만 남으니

이 값이 0보다 작아야 만족

 

3. h(n)의 n의 계수가 0보다 작을떄

이러면 무조건 조건을 만족할수 없겠다.

 

즉 조건문 한 큐로 문제는 끝난다.

f(n) ≤ c × g(n) AND N의 계수>=0 

이 조건 하나가 문제의 조건을 다 커버가능.

 

문제가 어렵지 않았던건 양의정수 n0이라서 양수부분만 따지면 ㅇㅋ

 

 

 

*INPUT의 조견.

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

다음 줄에 양의 정수 c가 주어진다. (1 ≤ c ≤ 100)

다음 줄에 양의 정수 n0가 주어진다. (1 ≤ n0 ≤ 100)

 

package 백준;
import java.util.*;
public class _24313_알고리즘점근적표기 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a1 = sc.nextInt(); //n의 계수
		int a0 = sc.nextInt(); //fn의 상수 둘다 정수
		
		int g계수 = sc.nextInt(); //양의 정수
		int n = sc.nextInt(); //양의 정수 range
		
		int gf=(g계수-a1)*n-a0;
		int n의계수 = g계수-a1;
		
		if(a1*n+a0<=g계수*n && n의계수 >=0 ) {
			System.out.println(1);
		}
		else {
			System.out.println(0);
		}
		sc.close();
		
	}

}