[BOJ] 백준 24314번 Python

백준 24314번 Python

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

 

문제

---

오늘도 서준이는 점근적 표기 수업 조교를 하고 있다.

아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해 보자.

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

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

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

함수 f(n) = a1n + a0, 양의 정수 c, n0가 주어질 경우 Ω(n) 정의를 만족하는지 알아보자.

 

 

입력

---

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

다음 줄에 양의 정수 c가 주어진다. (1 ≤ c ≤ 100)

다음 줄에 양의 정수 n0가 주어진다. (1 ≤ n0 ≤ 100)

 

 

출력

---

f(n), c, n0가 Ω(n) 정의를 만족하면 1, 아니면 0을 출력한다.

 

반응형

풀이

---

""" 첫 번째 정답 코드 """
import sys
input = sys.stdin.readline

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

ans = 1
for i in range(n0, 101):
    if (c*i)>(a1*i+a0) :
        ans = 0
        break

print(ans)

 

728x90

문제를 그대로 따라 코드로 작성하면 다음과 같은 코드가 나온다.

 

n0를 주어진 조건에 따라 하나하나 대입하며 식이 성립하는지 확인하는 방식이다.

 

해당 문제에서는 주어진 숫자가 작아 문제를 직관적으로 풀어도 문제가 없지만 입력값이 많아진다면 연산에 부담이 간다.

 

조금 더 나은(?) 코드를 작성하기 위해 수학적 접근을 해보자.

 

입력 조건을 다시 한번 살펴보자.

 

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

다음 줄에 양의 정수 c가 주어진다. (1 ≤ c ≤ 100)

다음 줄에 양의 정수 n0가 주어진다. (1 ≤ n0 ≤ 100)

 

해당 조건을 보고 조금만 생각을 한다면 다음과 같은 코드를 작성할 수 있다.

 

""" 두 번째 정답 코드 """
import sys
input = sys.stdin.readline

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

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

 

모든 값을 확인하지 않고 경곗값 그리고  c와 a1의 관계만 확인해도 Ω(n) 정의를 만족하는지 확인할 수 있다.

---

3항 연산자 표현이 조금 낯설게 느껴질 수 있다.

 

잠깐 3항 연산자에 대해 짚어보고 가자.

 

[condition] ? [true_value] : [flase_vlaue]

 

많은 언어들은 다음과 같은 삼항 연산자를 지원한다.

 

다만, 파이썬의 표현방식은 다음과 같다.

 

[true_value] if [condition] else [false_value]

 

조건문이 참일 때 true_value를 거짓일 때 false_value를 반환한다.

 

처음에는 어색할 수 있지만 사용하다 보면 익숙해진다.

 

코드도 간결해진다.

 

(조금 멋있어 보인다.)

---

각설하고 문제풀이로 돌아가자.

 

해당문제에서 배운 Big-Omega 표기법(점근적 하한 표기)에 관한 문제였다.

 

Big-O 표기법(점근적 상한 표기)을 활용해 문제를 바라보자.

 

첫 번째 코드는 O(n)의 시간복잡도를 가지는 코드이다.

 

두 번째 코드는 n의 범위가 넓어져도 실행시간이 일정한 O(1)의 시간복잡도를 가지는 코드이다.

 

해당문제는 n의 범위가 작았기 때문에 실행시간에는 큰 차이가 없지만,

 

지금부터 효율적인 코드를 작성하는 연습을 해야 이후에 시간제한 조건이 까다로운 문제를 해결할 수 있을 것이다.

 

 

Big-O 표기법은 알고리즘 문제를 풀 때 중요한 개념이므로 알아두면 좋을 것 같다.

 

참고 : https://en.wikipedia.org/wiki/Big_O_notation

Big O notation - Wikipedia