[코딩테스트] 백준 - 알고리즘 수업 - 점근적 표기 1

알고리즘 수업 - 점근적 표기 1 24313번 [6일차]

시간제한	메모리 제한
1초	512MB

문제

오늘도 서준이는 점근적 표기 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다}함수 f(n) = a1n + a0, 양의 정수 c, n0가 주어질 경우 O(n) 정의를 만족하는지 알아보자.

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

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

 

입력

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

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

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

 

 

출력

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

 

나의코드

package day6;

import java.util.Scanner;
import java.util.StringTokenizer;

public class Solution2 {

    // 알고리즘 수업 - 점근적 표기 1 24313번
    // 함수 f(n) = a1n+a0 = O(g(n))
    // 첫번째 줄 정수 a1 / a0
    // 두번째 줄 정수 c
    // 세번째 줄 n0
    // 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인

    // 7 7
    // 8
    // 1

    // f(n) = 7n+7
    // g(n) = n
    // c = 8;
    // n0 = 1
    // f(1) = 14
    // c* g(1) = 8
    //

    public static void main(String[] args) {

        // n을 구하는 공식
        // g(n) = n

        // n0 = 세번째줄

        // f(n)  ≤ c × g(n)
        // f(n) = a1 + a0 => 첫번째줄 숫자 2개

        // c = 두번째줄

        // n > n0
        // a1*n + a0 ≤ c * n; -> 해당 값이 맞는지 확인 하기



        Scanner sc = new Scanner(System.in);
        StringTokenizer st = new StringTokenizer(sc.nextLine());

        int a1 = Integer.parseInt(st.nextToken());
        int a0 = Integer.parseInt(st.nextToken());

        int c = Integer.parseInt(sc.nextLine());
        int n0 = Integer.parseInt(sc.nextLine());

        sc.close();

        // a0 <= c*n - a1*n
        // a0 <= (c - a1) *n
        // c는 양의 정수 이기 때문에 c > a1
        //
        if (c >= a1 && a0 <= (c - a1) * n0) { // 참이면
           System.out.println(1);
       }else {
           System.out.println(0);
       }
    }
}