5287. 파이썬 SW 문제해결 최적화 6일차 - 모의 담금질

태그 잊지 않고 붙이세요
#Algorithm #sw_expert_academy #D3 #Solved
문제 링크

제한사항

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50

다음 줄부터 테스트 케이스의 별로 T, T_end, k가 주어진다.

1<=T<=10000, 0＜T_end＜= 1, 0.8 ＜= k ＜ 1

문제 정리

함정 문제다. 문제 초반에 python 코드를 주고 비용이랑 이전 비용 차이 cost 함수 등 많은 정보를 주지만 다 필요 없는 내용이다.
우리가 구할 값은 T에 K를 몇 번 곱하면 T_end보다 작아지느냐다.
예제 1은 1000 0.1 0.8이 주어진다. 여기서 1000에 0.8^42의 값이 0.1보다 작아진다.

접근 방법

단순하게 반복문으로 T_end보다 작아질 때까지 곱한다. 이걸로 통과된다.

복잡도

시간복잡도는 x를 반복횟수라고 생각했을 때
$T * k^x < Tend$
$x < {ln(Tend) - ln(T)}/(lnk)$
$O({ln(Tend) - ln(T)}/(lnk))$가 된다.

코드

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # T가 T_end보다 작아지기 위해선 k를 몇번 거듭 곱해야 하나?
    T, T_end, k = map(float, input().split())
    count = 0
    while T > T_end:
        T = T * k
        count = count + 1

    print(f"#{test_case} {count}")

후기

만약, 출제자가 위 풀이 방법을 의도했다면 안 좋은 문제라고 생각한다.
k의 값이 1보다 작다는 건. 1에 한없이 가까운 값도 허용한다는 뜻이다.
예를 들어, k의 값이 0.9999999999999999999999999999999999라고 해보자. 실질적인 연산 횟수는 무한대에 가까워진다.
즉, 소수점 자리수 제한이 없다면 이 문제는 위 풀이 방법 시간복잡도론 절대 통과할 수 없다.[^1]
물론, 언어 별로 부동 소수점 자리수 제한이 있다. 하지만 그건 해당 언어의 특성이다. 알고리즘은 특정 언어에 종속되지 않아야 하지 않을까.

[^1]: 10000 0.0001 0.9999999를 입력하고 출력에 얼마나 시간이 걸리는지 확인해봐라.