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

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

 

💡문제 분석 요약

문제

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

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

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

이 정의는 실제 O-표기법(https://en.wikipedia.org/wiki/Big_O_notation)과 다를 수 있다.

함수 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을 출력한다.

💡알고리즘 설계

1. a1, a0, c, n을 입력받는다.
2. a1n+a0≤cn이고 a1≤c일 경우 1을, 아니면 0을 출력한다.

여기서 a1≤c가 꼭 들어가야한다.

f(n)=a1n+a0, g(n)=n이므로, f(n)≤cn이 된다.

1. a1n+a0≤cn 을 정리하면 a1+a0/n≤c가 되는데, a0이 0에 가깝거나 n이 무한대로 커질 경우 a1≤n에 가까워진다.
2. 직선의 방정식으로 그래프를 그려볼 경우, 기울기 a1이 기울기 c보다 크면 a0이 아무리 작은 음수라고 하여도 n이 커지면 언젠가는 f(n)이 g(n)보다 커진다.

이 부분이 이해가 잘 안되어서 검색을 해봤는데 대체로 ‘a0이 음수일 수 있으므로 a1≤c를 넣어야 한다’ 라고 설명하고 있었다.

O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다} 에서 ‘모든 n’이라는 단어에 집중하면 이해가 좀 더 쉬울 것 같다.

a0이 음수고 a1이 c보다 큰 경우에, 식에 n0을 넣었을 때는 f(n)≤cn으로 옳게 나올 수 있으나, n이 점점 커져 100이 되었을 때는 f(n)>cn이 될 수 있다.

 

a1=7, a0=7, c=8, n0=10인 경우이다.

• g(10) = 8×10 = 80 (파란점)
• f(10) = 7×10 + 7 = 77 (빨간점)

g(n)이 f(n)보다 항상 값이 크다.

 

클로드한테 그래프 그려달라고 시켰더니 모양이 조금 이상하긴 한데… 유료 결제를 안 한 탓인가 싶으니 넘어가도록 하자

 

 

a1=7, a0=-15, c=6, n0=10인 경우이다.

• g(10) = 6×10 = 60 (파란점)
• f(10) = 7×10 + -15 = 55 (빨간점)

• g(100) = 6×100 = 600 (파란점)
• f(100) = 7×100 + -15 = 685 (빨간점)

n0에서는 cn이 f(n)보다 높게 있지만, n이 100까지 가면 cn이 f(n)보다 값이 작아져서 결국 답이 맞지 않게 된다.

a1*n+a0<=c*n으로만 답을 판단하면 1을 출력하지만, a1*100+a0<=c*100으로 답을 판단하면 0이 된다.

그래서 a1<=c 조건을 넣거나, a1*100+a0<=c*100 조건을 넣어야 한다. (100인 이유는 문제의 n 범위가 1≤n≤100 이었기 때문에..)

💡코드

a1, a0 = map(int, input().split())
c = int(input())
n = int(input())

print(1) if a1*n+a0<=c*n and a1<=c else print(0)

const readline = require("readline");

(async () => {
  let rl = readline.createInterface({ input: process.stdin });
  const lines = [];
  let counter = 3;
  for await (const line of rl) {
    lines.push(line.split(" ").map(Number));
    counter--;
    if (counter == 0) rl.close();
  }
  const [a1, a0] = lines[0];
  const c = lines[1];
  const n = lines[2];

  console.log(a1 * n + a0 <= c * n && a1 <= c ? 1 : 0);
})();

💡 느낀점 or 기억할 정보

그래프는 클로드한테 그려달라고 시켜봤는데 gpt가 더 잘그리는 것 같다! 다음에는 gpt를 이용해보아야겠다.