[파이썬/python] 백준 24313번 : 알고리즘 수업 - 점근적 표기 1(🥈4)

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

cnt = 0

for i in range(n0,101):
    if a1*i + a2 <= c * i:
        cnt += 1

if cnt == 101 - n0:
    print(1)
else:
    print(0)

처음에 풀었던 방식

그냥 문제에 나와있는 공식을 잘 보고 대입하면 답이 나와서 문제 자체를 푸는 거에는 어려움이 없었는데 정석적인 답이랑은 거리가 멀 것 같아서 좀더 찾아보았다.

 

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

if a1*n0 + a2 <= c * n0 and c >= a1:
    print(1)
else:
    print(0)

정석적인 풀이는 이거같다

c 가 a1보다 커야 한다는 걸 알면 더 간단하게 풀 수 있는데 왜 저런 조건이 붙는지 이해가 가지 않았다

찾아보니까

https://blog.naver.com/purplecow7/223028888165

백준 시간 복잡도 24313 - 파이썬

이렇다고 한다

그러니까 만약 c가 a1보다 작다면 그래프에서 c * g(n)의 값이 f(n)보다 커지게 되는 순간이 있기 때문에 저런 조건을 붙여줘야 한다고 함

 

이렇게 시간복잡도 단계 끝!