[python_파이썬_이해안감]백준_24313번_알고리즘 수업 - 점근적 표기1_풀이

공부하는 허딩크 : https://www.youtube.com/live/qRYajWJrQv8?feature=shared

이번에도 문제 이해가 힘들다.

천천히 반복해서 읽어보자. 예제까지 잘 읽어보자.

문제의 맨 마지막에 문구가 "O(n)의 정의를 만족하는지 알아보자" 이다.

첫번째 예제에서는 f(n) = 7n + 7, g(n) = n, c = 8, n0 = 1이어서, f(1) = 14, c * g(1) = 8임으로 O(n)의 정의를 불만족한다는 설명히 있다. 두번째 예제는 이 공식으로 만족한다는 설명이 있다.

 

일단 파이썬에서는 돌아가는데 틀렸다. 뭐가 문제인지 분석해보자.

<첫번째 시도 : 틀렸습니다.>

import sys

input = sys.stdin.readline

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

c = int(input())

n0 = int(input())

print(int((a1 * n0) + a0 <= c * n0))

   

 

<두번째 시도 : 틀렸습니다.>

a1, a0가 0이상의 조건이 있어서 abs()를 줬는데 이건 답이 아니네.

import sys

input = sys.stdin.readline

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

c = int(input())

n0 = int(input())

print(int((abs(a1) * n0) + abs(a0) <= c * n0))

 

질문 게시판을 보니 조건이 하나 더 붙어야 하는데 그 조건이 왜 나오는지 찾기가 어렵네..

왜 a1 <= c가 나와야 하는 걸까??? abs()로 해줘도 값을 동일한거 같은데.....

c는 양의 정수고 a1는 음의 정수"도"가능하다.

즉 a1보다 c는 무조건 크거나 같아야 한다???? 이게 이해가 되나???

다른 해설들은 이 부분이 그냥 나오는데 나는 이해가 안되는데.....

<세번째 시도 : 정답>

import sys

input = sys.stdin.readline

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

c = int(input())

n0 = int(input())

print(int((a1 * n0) + a0 <= c * n0 and (a1 <= c)))

 

<설명 : https://bakjoon-coding.tistory.com/32#google_vignette>

이분이 잘 설명해주었다. 근데 난 이해가 어렵다......10번을 읽어도 이해가 안됨.

1. n >= n0 이부분이 포인트 인 것 같다. => n이 변화에 따라 참/거짓이 달라지면 안된다는 건가??

반례로 a1 = 4, a0 = -3, c = 3, n0 = 1인 경우

4 * 1 - 3 <= 3 * 1이 만족해서 답은 1이 나온다.

하지만 n = 7일 경우

4 * 7 - 3 <= 3 * 7이 만족을 하지 않아 답은 0이 나온다.

여기까지 아직 이해 못했다.... 이럴때는 내일 다시 봐야지.