[BaekJoon] 24313번 알고리즘 수업 - 점근적 표기 1 문제풀이 (Success)

24313번: 알고리즘 수업 - 점근적 표기 1

 

☕Language: Java

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    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 A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
 
        int C = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());
        
        int x = 1;
        for (x = 1; x <= N; x++) {
            if ((C - A) * x >= B) {
                break;
            }
        }
 
        if (x <= N && A<=C) {
            bw.write("1");
        } else {
            bw.write("0");
        }
 
        bw.flush();
        bw.close();
    }
 
}
 

🤔 해설

1. for 반복문

    - 수식을 만족하는 x가 있을 경우, N과 비교하여 O(n)을 만족하는지 판단

🚨 A<=C 조건식 추가

 ax + b <= cx

b<=(c-a)x

에서 x의 범위를 살펴보기 위해서 총 3가지 가능성 고려

    - c=a

        - 특정값 이상의 모든 x에 대해서 부등식을 만족할 수 있음

        - 예: b=0일 경우, N과 무관하여 N보다 크거나 같은 모든 x에 대해서 부등식 만족

    - c>a

        - b/(c-a)<=x에서 b/(c-a)보다 크거나 같고 x보다 작거나 같은 N을 찾을 수 있음

        - 예: b=10, c=2, a=1일 경우, N>=10까지 O(n)을 만족

            - N=9일 경우, x가 9인 경우부터 판단할 수 있는데 부등식을 만족하지 않으므로 O(n) 불만족

    - c<a

        - b/(c-a)>=x에서 x는 N보다 크거나 같은 수로 값의 범위가 없으므로 양의 무한대까지 커질 수 있음

        - c<a를 만족하는 x가 있을 수 없음

        - O(n)을 판별하는 조건식에서 c<a일 경우는 N값과 무관하게 무조건 불만족

 

😮 이 외의 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    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 A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
 
        int C = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());
 
        int fn = A * N + B;
        int gn = C * N;
 
        if (C >= A && fn <= gn) {
            bw.write("1");
        } else {
            bw.write("0");
        }
 
        bw.flush();
        bw.close();
    }
 
}
 

- for 반복문 사용하지 않고, 조건식으로 판별

 

 

 

🔗 소스 코드
HJ0216/TIL/BOJ

 

📚 참고 자료

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