📌 문제

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

오늘도 서준이는 점근적 표기 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

알고리즘의 소요 시간을 나타내는 O-표기법(빅-오)을 다음과 같이 정의하자.

O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다}

이 정의는 제 O-표기법과 다를 수 있다.

함수 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), c, n0가 O(n) 정의를 만족하면 1, 아니면 0을 출력한다.

💡 코드

✅ 처음에 문제만 봤을 땐 이게 뭔 소린가,, 싶었데 예제의 설명을 참고하여 다시 보면 함수 f(n), g(n)은 f(n) = a1*n + a0, g(n) = n로 정의할 수 있고, n0 이상의 모든 양수에 대하여 f(n) ≤ c * g(n)인 경우 O(n)의 정의를 만족한다고 할 수 있다.

범위 내의 최솟값인 n0을 대입했을 때 조건을 만족하면 그 이상의 모든 수에 대해서도 조건을 만족하므로 O(n) 정의를 만족한다고 할 수 있다. 만약, 그 이상의 수가 조건을 만족하더라도 최솟값인 n0가 조건을 만족하지 못한다면 O(n) 정의를 만족한다고 할 수 없다.

❌ 분명 전체적인 로직은 맞는 것 같은데 오답 처리 됐다,, 어째서인가,, 하다가 다시 보니 0 ≤ |ai| ≤ 100 여기서 절댓값 표시를 흐린눈하고 양수만 입력받는다고 생각헀다,, 저 범위를 다시 풀어 쓰면 -100 ≤ ai ≤ 100이 되기 때문에 ai가 음수인 경우를 고려하지 않아서 틀리지 않았을까? 라고 생각해봄

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());
		
		if((a1 * n0 + a0) <= (c * n0)) bw.write("1");
		else bw.write("0");
		
		br.close();
		bw.close();
	}
}

✅ 생각해보다 모르겠어서 구글링의 힘을 빌려 해결했다,,

우선 내가 위에서 생각했던 범위 내의 최솟값 n0을 대입했을 때 조건을 만족하면 그 이상의 모든 수에 대해서도 조건을 만족한다. 는 ai가 모두 양수일 때만 해당하는 가설이였다!

먼저, a1이 음수인 경우에는 위 가설과 같이 n0이 만족하지 못하여도 n0 이상의 수에서 조건을 만족할 수 있는 형태이므로 어차피 n0에서 조건을 만족하지 못하면 걸러지므로 제대로 된 답을 도출할 수 있으므로 크게 문제가 되지 않는다.

하지만 a0이 음수인 경우는 위 가설과 반대로 n0이 조건을 만족해도, n0 이상의 수 가 조건을 만족하지 않을 수 있는 형태이므로, n0 이상의 수 에서 만족하지 않는 경우를 걸러낼 수 없어서 문제가 된다! 따라서, 추가 조건 c >= a1을 함께 판별해줘야 한다.

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());
		
		if((a1 * n0 + a0) <= (c * n0) && c >= a1) bw.write("1");
		else bw.write("0");
		
		br.close();
		bw.close();
	}
}