백준 24313번- '알고리즘 수업 - 점근적 표기 1' (PYTHON 풀이)

문제:

시간 복잡도의 마지막 문제이다. 역시나 가장 어려운 문제여서 그런지 이해하는 것부터 조금 힘들었다. 고민하다가 도저히 모르겠어서 구글링과 질문 게시판을 활용해서 문제를 풀었다. 참고한 내용들을 바탕으로 정리를 해보겠다.

 

문제에서 주는 함수는 f(n) = a1 * n + a0 이고, 비교 대상 함수는 g(n) = n 이다.

문제를 풀기 위해서는 주어진 a1, a0, c, n0가 주어진 c와 n0로 모든 n ≥ n0에 대해 a1n + a0 ≤ cn 인지 확인해야한다.

결과적으로 확인해야 할 식은 모든 n ≥ n0에 대해 a1 * n + a0 ≤ c * n 가 성립하는지 보는 것이고, 이를 정리하면 (a1 - c) * n + a0 ≤ 0가 된다. 이렇게 하면 끝이 아니라 (a1 - c)의 부호에 따라 가능 경우를 확인해보아야 한다.

 

1) a1 > c 인 경우

-> (a1 - c)가 양수이므로 왼쪽 식은 n이 커질수록 값이 커진다. 결국 n이 충분히 커지면 (a1 - c)*n + a0 는 양수가 되어 ≤ 0이 될 수 없다.

-> 따라서 a1 > c 이면 모든 n ≥ n0에서 성립할 수 없어서 답은 0이다.

2) a1 == c 인 경우

-> (a1 - c) = 0 이므로 부등식은 단순히 a0 ≤ 0 이 되어, a0가 0 이하일 때만 모든 n에 대해 성립한다.

-> 따라서 a1 == c 면 a0 ≤ 0 이어야 답이 1이다.

3) a1 < c 인 경우

-> (a1 - c)가 음수라서 왼쪽 값은 n이 커질수록 작아진다. 즉 n이 증가하면 부등식이 더 쉽게 성립한다.

-> 그러므로 가장 가능한 문제점(=가장 큰 값)이 되는 지점은 가장 작은 n, 즉 n = n0 이다. 따라서 n = n0에서 부등식이 성립하면 모든 n ≥ n0에서 성립한다.

 

따라서 모든 경우를 한 줄로 정리하면 다음과 같다.

(a1 * n0 + a0) ≤ (c * n0) 이고 동시에 a1 ≤ c 이면 출력 1, 그렇지 않으면 0

 

 

풀이:

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

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

문제 정리 부분에서 설명한대로 그대로 적기만 하면 되어서 더이상 설명할 것은 없다.

역시 문제만 이해하면 코드는 어렵지 않은 문제이다,,