백준 24313번 - BigO표기법 문제설명 - Java

문제 핵심 포인트

1. 문제를 이해하는 것 부터 힘들다.

2. 숨은 조건을 찾아내기

 

• 일단 아래에 중요한 부분을 표시해봤다.

 

여기서 O(n)정의를 만족하는지를 물었으니 O(g(n))의 g(n)은 n이 된다.

+ 문제조건

1. a1,a0 = 양수,음수 가능

2. c,n0 = 양수

이 정보들을 바탕으로 부등식을 써보자

 

a1*n0 + a0 ≤ c*n0

 

이 부등식을 조건문으로 사용해서 문제를 제출해보자. 정답인 것 같다.

import java.io.*;
public class Main {
    public static void main(String[] length) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] arr = br.readLine().split(" ");
        int a1 = Integer.parseInt(arr[0]);
        int a0 = Integer.parseInt(arr[1]);
        int c = Integer.parseInt(br.readLine());
        int n0 = Integer.parseInt(br.readLine());

        int fn = a1*n0 + a0;
        int gn = n0;
        int cgn = c*gn;

        if(fn<=cgn)bw.write("1");
        else bw.write("0");

        bw.flush();
        bw.close();
        br.close();

    }
}

 

어림도 없이 틀렸다는 결과를 받아볼 수 있다. 그럼 왜 틀렸냐? 숨은 조건을 찾지 못했기 때문이다. 아까 부등식을 다시 살펴보자.

a1*n0 + a0 ≤ c*n0 이 부등식을 다시 정리해보면

 

a1*n0 + a0 ≤ c*n0 ------> a0≤(c-a1)n0 이렇게 정리할 수 있다.

 

근데 문제에서 정의한 O(g(n))의 결과가 참이기 위해서는 n0가 계속 커져도 부등식의 등호가 변하면 안된다.

그렇게 하기 위한 조건은? c-a1가 양수이면 가능하다. 이해하기 쉽게 양수가 아닌 경우를 예로 들자면

 

a0가 -50 , c-a1=-1, n0=1이라고 가정하자.

처음에는 n = n0 = 1이면 -50 ≤ -1 이니까 참 → “1”이 출력된다.

하지만 n0의 위에 있는 수 n이 60이라면? -50 ≤ -60은 거짓 → “0”을 출력하게 된다.

 

위와 같은 상황을 막기 위해 c-a1가 양수라는 조건을 추가한 조건문을 사용하면 통과된 결과를 볼 수 있다.

import java.io.*;
public class Main {
    public static void main(String[] length) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] arr = br.readLine().split(" ");
        int a1 = Integer.parseInt(arr[0]);
        int a0 = Integer.parseInt(arr[1]);
        int c = Integer.parseInt(br.readLine());
        int n0 = Integer.parseInt(br.readLine());

        int fn = a1*n0 + a0;
        int gn = n0;
        int cgn = c*gn;
	//조건 추가
        if(fn<=cgn&&a1<=c)bw.write("1");
        else bw.write("0");

        bw.flush();
        bw.close();
        br.close();

    }
}