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

문제

• O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다}
• 함수 f(n) = a1n + a0, 양의 정수 c, n0가 주어질 경우 O(n) 정의를 만족하는지 알아보자.

입력

• 첫째 줄에 함수 f(n)을 나타내는 정수 a1, a0가 주어진다. (0 ≤ |ai| ≤ 100)
• 다음 줄에 양의 정수 c가 주어진다. (1 ≤ c ≤ 100)
• 다음 줄에 양의 정수 n0가 주어진다. (1 ≤ n0 ≤ 100)

문제 해석

• 콘솔로부터 f(n)의 a1과 a0, c, n을 입력받해당 알고리즘은 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)을 만족하는 지(1) 아닌지(0) 를 출력하면 된다.

• 예시

• 이런식으로 계산했을 때, 맨 아래의 비교식의 참, 거짓을 따지면된다.

틀린 코드

import java.io.*;
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 a1 = Integer.parseInt(st.nextToken());
        int a0 = Integer.parseInt(st.nextToken());

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

        boolean result = true;
        
        while(n <= n0){
            if(a1*n0 + a0 > c*n0){
                result = false;
                break;
            }
            n++;
        }

        if(result) {
            bw.write(1 + "");
        }else{
            bw.write(0 + "");
        }
        bw.flush();
        bw.close();

    }
}

• 입력받은 수를 계산해서 만족하지 않은 경우 while문 밖에 있는 변수에 false를 넣어서 break걸면 하나라도 만족하지 않는 경우를 거른거니까... 이렇게 짜면 되겠다 싶어서 작성했지만...

결과1

• 틀렸다... (틀린 이유를 모르겠고, 이유를 몰라서 코드를 고칠 수가 없어 다른분이 한 코드를 보고, 이해하여 작성하였다.)

코드(참고)

import java.io.*;
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 a1 = Integer.parseInt(st.nextToken());
        int a0 = Integer.parseInt(st.nextToken());

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

        if (a1*n0 + a0 <= c*n0 && c >= a1) { //참인 경우를 if문으로 만들어 작성한 것을 볼 수 있다.
            bw.write("1");
        } else {
            bw.write("0");
        }

        bw.flush();
        bw.close();

    }
}

• 여기서 참고한 코드에서는 while문을 쓰지 않았고, 비교식은 한번만 실행한다.
• 그래서, 비교식을 하나 더 추가해야하는데, 그 이유는 a₀이 음수 일 경우 문제가 생기기 때문이다.

• n을 1을 입력받으면 해당 만족여부를 거를 수가 없다.
• 그래서 조건을 a₁<= c를 걸어준 것 같다.
• 그렇게 되면, 왼쪽은 오른쪽보다 절대 커질 수 없기때문에!

결과

느낀점

• 코드를 작성하면서 맞게 작성한 것 같은데 틀리고... 다른 사람코드를 보고 아 이런식으로 했구나! 라고는 알겠지만, 100%는 이해하지 못해서 이 문제는 나중에 한번 다시 봐야할 것 같다.😢

.. 우연히 이 포스트를 보게 되신다면, 이 문제 설명 부탁드립니다. (뭔가 제대로 이해한건지 헷갈려서 모르겠네요..) 😢😢😢😢