백준 24313 - 알고리즘 수업 - 점근적 표기1.py

문제

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

알고리즘의 소요 시간을 나타내는 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. 식 변형

2. 조건 (음수, 양수, 0)

 

3. 조건에 따라 변하는 것

을 잘 살펴보는 게 중요한 것 같다.

 

이 문제에서 나의 맹점

입력 조건인 a1, a0가 ~100부터 +100 (0포함) 값이라는 것이다.

식 변형에서 음수나 0에 따른 부호변화.. 를 면밀히 살피지 못 했다.

또한 n >= n0의 모든 n이라는 점에서, n은 n0를 시작으로 계속 증가하는 값 이라는 데에 신경을 썼어야 했는데 이 점을 알아차리지 못 한 점..

 

이 두 조건을 생각하다보면 a0가 음수일 때 문제가 발생한다는 점.

또한 식 변형을 했을 때 a1*n = c*n - a0 에서 n으로 나누면 a0/n <= c-a1 의 식을 얻을 수 있다.

(n은 무조건 양수이기 때문에 마음대로 나누어도 된다는 점)

여기서 n이 증가함으로써 왼쪽 식인 a0/n는 0으로 가까워진다는 것을 알 수 있다. 그럼 c-a1 >= 0을 얻어.. c >= a1의 조건을 얻을 수 있다. 

 

이렇게 부호에 따른 식 변형 / 분모가 무한대로 커질 때 그 값은 0으로 간다는 점을 유의해서 수학식을 변형해보자 ..!! 

 

다음은 해법 코드이다.

헤맨 것 치고 너무 간단한.. 고등수학 + 간단한 조건 코드여서 자괴감이 .. ^^ 수학식 더 많이 연습하자.

import sys

a1, a0 = map(int,sys.stdin.readline().split())
c = int(sys.stdin.readline())
x1 = int(sys.stdin.readline())

if a*x1 + a0 <= c*x1 and a1 <= c:
    print(1)
else:
    print(0)