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

🔗 문제 개요

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

---

📌 문제 개요

함수 f(n) = a1\*n + a0 이 주어졌을 때,

 

f(n) ≤ c\*n 을 만족하여 O(n) 인지 판단하는 문제이다.

 

조건 : n ≥ n0

 

이 조건을 만족하는 모든 n에 대해 성립해야 한다.

---

📌 접근 방법

Big-O 정의를 그대로 코드로 구현하면 된다.

 

조건 : f(n) ≤ c\*n

 

여기서 f(n) = a1\*n + a0 이므로 a1\*n + a0 ≤ c\*n 이 된다.

 

그리고 문제에서 n ≥ n0 이므로 n = n0일 때 성립하는지만 확인하면 된다.

---

📌 핵심 아이디어

a1\*n + a0 ≤ c\*n  
a0 ≤ (c - a1)\*n

 

 

1️⃣ a1 ≤ c
2️⃣ a1*n0 + a0 ≤ c*n0

 

이 두 조건을 만족하면 O(n) 이다.

---

📌 전체 코드

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

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

---

📌 정리

이 문제는 점근적 표기 O(n)의 정의를 이해하고 있는지 확인하는 문제이다.

핵심 조건은 다음 두 가지이다.

a1 ≤ c
a1*n0 + a0 ≤ c*n0

 

이 두 조건을 만족하면 O(n) 이므로 1을 출력하고, 만족하지 않으면 0을 출력한다