[알고리즘]1712번: 손익분기점

알고리즘 유형: 수학

문제

월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 인건비 등 총 B만원의 가변 비용이 든다고 한다.

예를 들어 A=1,000, B=70이라고 하자. 이 경우 노트북을 한 대 생산하는 데는 총 1,070만원이 들며, 열 대 생산하는 데는 총 1,700만원이 든다.

노트북 가격이 C만원으로 책정되었다고 한다. 일반적으로 생산 대수를 늘려 가다 보면 어느 순간 총 수입(판매비용)이 총 비용(=고정비용+가변비용)보다 많아지게 된다. 최초로 총 수입이 총 비용보다 많아져 이익이 발생하는 지점을 손익분기점(BREAK-EVEN POINT)이라고 한다.

A, B, C가 주어졌을 때, 손익분기점을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 21억 이하의 자연수이다.

출력

첫 번째 줄에 손익분기점 즉 최초로 이익이 발생하는 판매량을 출력한다. 손익분기점이 존재하지 않으면 -1을 출력한다.

 

풀이

 

while을 사용해서 하나씩 더해주면 가능한 n의 범위가 21억개까지이므로 시간초과가 걸립니다.

1-5초를 기준으로 1억개까지 $$O(N)$$으로 통과가 가능한데 저희 같은 경우 시간도 0.35초까지이므로, 

더 타이트하게 잡아야합니다  

시간 복잡도에 대한 자세한 내용은 아래 포스팅 참고 바라겠습니다 

 

https://kjim.tistory.com/45

[알고리즘]알고리즘의 복잡도와 설계 ti

 

한번씩 더해주는게 아니라 한번에 1000대를 판것처럼 더해주겠습니다 

그다음 다시 손익분기점까지 한개씩 빼주는 과정을 반복합니다

 

이렇게 진행하면 최소값에서는 손해를 볼 수도 있지만 최대 계산이 N인 21억이 아니라 210만번에서 끝낼 수 있습니다.

 

from sys import stdin

loss, loss_per, price= map(int,stdin.readline().strip().split(" "))
profit=0
cnt=0
if price>loss_per:
    while loss>=profit:
        loss+=1000*loss_per
        profit+=1000*price
        cnt+=1000
    loss-= 1000*loss_per
    profit-=1000*price
    cnt-=1000
    while loss>=profit:
        loss+=loss_per
        profit+=price
        cnt+=1
    
    print(cnt)
else:
    print(-1)