[Python] 백준 1712번(손익분기점) 문제 풀이

 

 쉽게 풀릴 것만 같았는데 생각을 좀 해봐야 풀리는 문제였다.

 

 처음에는 코드를 이렇게 짰다.

 

a, b, c = list(map(int, input().split()))
production_price = a
revenue = 0
i = 0
if b >= c:
    print(-1)
else:
    while True:
        i += 1
        production_price += b
        revenue += c
        if production_price < revenue:
            print(i)
            break

 

 그랬더니 시간초과가 났다. 당연히 제한시간이 0.35초인데 <예제 입력 3>만 봐도 2100000001번 반복문을 돌려야 하는 비효율적인 코드였던 것이다. 그래서 생각을 좀 해본 뒤에 코드를 다시 짰다.

 

a, b, c = list(map(int, input().split()))
if b >= c:
    print(-1)
else:
    print(int(-a/(b-c)) + 1)

 

 부등식을 이용하면 풀리는 문제였다.

 

 a+bx<cx 를 만족시키는 가장 작은 정수 n을 구한다고 생각하면 쉽다. 우변을 좌변으로 이항하면 a+(b-c)x<0 이다. 근데, a>0, x>0 이므로 b-c=0 이거나 b-c>0 이라면 해가 없다. 0보다 작아지려면 b-c<0 이어야 한다. 그럼 b-c=0 혹은 b-c>0 일 때에는 -1을 출력해주고, b-c<0 이라면 a+(b-c)x<0 에서 (b-c)x<-a, b-c<0 이므로 x>-a/(b-c) 가 된다. 이를 만족시키는 가장 작은 정수 n은 우변에 1을 더해준 값이 될 것이다.