24313번

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

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

이 문제는 점근적 표기법에 대한 문제이다. 시간복잡도의 빅오 함수를 정의하는 것인데,

처음에는 너무 쉽다 생각해서 바로 구현하여 돌렸는데, 91퍼에서 틀려서 뭐가 문제인가 생각하게 만든 문제이다.

이유는 생각보다 간단했다. 내가 생각한 로직은 g(n0)>=f(n0)이 성립하면 된다고 생각했다.

하지만 여기서 생각할 것은 f(n)<=g(n)이다. 즉 모든 n에 대해서 성립해야하는 조건이라는 것이다.

n0에서는 성립하지만 n1에서는 성립하지 않을 수 있다는 것이다.

그래서 여기서 주어져야 하는 조건은 a1이 c보다 작거나 같아야한다는 조건이다.

이 조건을 부여하면 n이 증가함에 따라 n0와의 조건식 결과가 달라지지 않는다.

 

정답 코드는 아래와 같다.

package backjoon.b24313;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class b24313 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a1 = Integer.parseInt(st.nextToken());
        int a0 = Integer.parseInt(st.nextToken());

        int c = Integer.parseInt(br.readLine());
        int n0 = Integer.parseInt(br.readLine());

        int fn = a1*n0+a0;
        int gn = c*n0;
        if(gn>=fn && a1<=c){
            System.out.println(1);
        }
        else System.out.println(0);
    }
}