[백준] 24313번: 알고리즘 수업 - 점근적 표기 1 - JAVA

[작성일: 2023. 10. 10]

 

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

 

 

풀이

import java.util.Scanner;
 
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();
 
        boolean bigO = true;
 
        for (int i = n0; i <= 100; i++) {
            if (a1 * i + a0 > c * i) {
                bigO = false;
                break;
            }
        }
 
        System.out.println(bigO ? 1 : 0);
    }
}

 

사실 이 문제는 아직도 이해가 잘 안 되는데 풀고나서 역으로 공부했다.

 

우선 f(n) = a1n + a0의 값을 c*n과 비교해야 한다. 만약 f(n)이 c*n보다 크거나 같다면 O(n) 정의를 만족하지 않는다. (f(n)이 c*n보다 항상 작거나 같다는 것을 의미한다.)

하지만 모든 n에 대해서는 검사할 필요가 없고, 문제에서 n >= n0인 경우메나 검사하면 된다고 했으므로 for문의 시작은 n0부터 100까지로 했다.

 

조건을 만족하지 않는다면 bigO 변수를 false로 설정하고 루프를 빠져나온다.