문제 출처

단계별로 풀어보기 > 시간 복잡도 > 알고리즘 수업 - 점근적 표기 1
https://www.acmicpc.net/problem/24313

문제 설명

f(n) = a1n + a2, c, n0 가 주어질 때, O(n) 정의에 만족하면 1, 아니면 0을 출력하라.

접근 방법

import java.io.*;
import java.util.StringTokenizer;

public class 알고리즘_수업_점근적_표기_1 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int a1 = Integer.parseInt(st.nextToken());
        int a2 = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());

        int c = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());

        int n0 = Integer.parseInt(st.nextToken());

        if(a1 * n0 + a2 <= c * n0 && c >= a1){
            bw.write("1");
        } else {
            bw.write("0");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

예제를 보고 문제를 이해했다.
a1 n0 + a2 <= c n0 의 식을 만족하는 경우 1을 출력하는데,
이 때 한가지 더 고려해야할 사항이 (0 ≤ |ai| ≤ 100) 의 조건으로 a1 <= c의 조건도 고려해야한다.

문제의 시간 복잡도는 입력과 조건문 밖에 없으므로, O(1)이다.

문제푼 흔적