[Java] 백준 24313 알고리즘 수업 - 점근적 표기 1 풀이 / 시간 복잡도

문제

시간 복잡도 개념 보러가기

 

 

풀이

우선 기본 공식을 알아보자. O(g(n)) 은 f(n) <= c * g(n) 이다. 이때, O(n) 을 알아보자 했으니 g(n) 은 n 이 된다. 그리고 f(n) = a1 * n + a0 이다. 

정리하면, a1 * n + a0 <= c * n 이 된다.

a1 * n + a0 <= c * n

 

그런데 이렇게 제출하면 틀렸습니다. 가 출력된다. 너무 모르겠어서 다른 사람들 블로그를 찾아봤다. 결론부터 말하자면 조건식에 아래 코드를 넣어줘야 한다고 한다.

&& a1 <= c

 

그런데 이 부분이 너무 이해가 안 갔다. 제대로 설명하는 사람이 거의 없었다. 

내가 이해한 대로 설명을 해보겠다. 혹시 틀리다면, 댓글로 알려주길 바랍니다!!

 

 

1. 나온 조건식을 전부 좌항으로 옮기면 아래와 같이 변경된다.

 

2. 이때, 문제에 나온 조건을 만족시켜야 한다.

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

나는 이를 n 이 어떤 값이건 위 공식이 만족되어야 한다는 의미로 이해했다.

 

3. 이를 만족시키는 조건은 a1 - c 에서 결정된다. n 과 a0이 양수건 음수건 상관없이 조건을 만족시켜야 한다.

* a1 - c < 0 인 경우 

a1 < c 일 때, a1 - c 는 음수가 된다. 이 경우, n 이 커질수록 좌항은 더 음수가 되어 항상 성립하게 된다.

 

* a1 - c > 0 인 경우

a1 > c 일 때, a1 - c 는 양수가 된다. 이 경우, n 이 커질수록 좌항의 값이 커져 부등식이 성립하지 가능성이 커진다. 따라서, 부등식이 항상 성립할 수 없다.

 

* a1 - c = 0 인 경우

a1 = c 일 때, 부등식은 a0 <= 0 으로 변형된다. 이 경우에는 a0이 0 이하일 때만 부등식이 성립한다.

 

위 경우에 따라, a1 - c < 0 인 경우에만 항상 성립하며, 나머지의 경우에는 성립하지 않는다. 하지만 a1 = c의 조건은 a0이 음수일 때만 성립하므로 a1 <= c 조건으로 추가해야한다.

* a0이 양수이면 else 로 빠져 0이 출력되기 때문이다 ! 음수일 때 성립할 수 있게 <= 조건으로 넣어줘야 한다.

 

 

아래 분이 내가 본 블로그 중에는 설명을 제일 잘 해주셨다.

https://rightbellboy.tistory.com/207

[백준/BOJ] 24313번 알고리즘 수업 - 점근적 표기 1 (C/C++)

 

 

 

코드

package AlgorithmStudy.src.bronze;

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

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

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

        if (1 > c || c > 100 || 1 > n || n > 100 ||
                0 > Math.abs(a1) || Math.abs(a1) > 100 || 0> Math.abs(a0) || Math.abs(a0) > 100) return;

        if ((a1 * n + a0) <= (c * n) && a1 <= c) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }
}