백준 24313번 (Java)

 

빅오 표기법의 정의를 기반으로 하는 복잡도 문제이다.

보통 어떤 함수를 빅오로 표현하면 계수를 제외하고 최고차항만 나타낸다.

 

 

정의에 따라 생각해보자면 O(g(n)) = f(n) 일때 c * g(n)이 f(n)의 상한값이라고 할 수 있다. (c는 상수이다)

 

 

예를 들어 g(n) = n 이고 f(n) = 2n+1 이라고 하면 

모든 n>= n0 에 대하여    f(n) <= c * g(n)     즉  2n+1 <= c*n 을 충족할 c값과 n0가 하나라도 존재하면

f(n) = O(g(n))      즉 2n+1 = O(n) 이라고 할 수 있다.

 

 

쉽게 말해서 n0구간 부터 f(n)이 g(n)보다 밑에 있다고 생각하면 되겠다.

 

 

 

여기서 조심할 점은 문제에서는 n0값과 c값을 제한하고 있다.

그 점을 유의하여 풀면 된다.

 

 

 

import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);

            int a1 = sc.nextInt();
            int a0 = sc.nextInt();
            int c = sc.nextInt();
            int n0 = sc.nextInt();

            if(a1*n0+a0 <= c*n0 ) System.out.println("1");
            else System.out.println("0");

            sc.close();
    }
}

하지만 위 코드는 틀 렸 다.

 

 

 

 

 

내가 간과한 점이 있다. 문제에서 a1과 a0 값이 음수 일수도 있다는 점이다.

 

 

 

그렇다는 말은 a0가 음수일때

처음에는 g(n)이 f(n)보다 크다가 일정 구간을 지나치면 f(n)이 g(n)을 역전할수도 있다는 것이다.

그렇다면 c 즉 g(n)의 기울기가 f(n)의 기울기보다 항상 크거나 같을 조건을 추가해주면 된다.

 

 

 

 

 

위코드에서

if(a1*n0+a0 <= c*n0 && a1 <= c) System.out.println("1");

이 부분만 고치면 되겠다.