[백준] 1712. 손익분기점

문제

https://www.acmicpc.net/problem/1712

풀이

"멍청하면 손발이 고생하면서 교훈을 얻게 된다." 

문제 조건이 21억인데, 시간복잡도가 O(n)이라고 해도 21억번의 연산을 거쳐야하므로 시간이 오래걸린다. 컴퓨터는 1초에 대략 10^8번의 연산이 가능하므로 훨씬 더 많은 연산이 요구된다. 따라서 이분 탐색을 이용하면 더 빠르게 풀 수 있겠다는 생각으로 이분 탐색을 이용하여 해결했다.

뭔가 느낌이 이상했다. solved.ac 기준 매우 쉬운 문제로 분류되어 있는데, 이분 탐색의 난이도는 아니였다. 자세히 보니 문제 분류가 '수학'으로 되어 있다. 사실 이 문제는 중학교 교육과정으로 해결할 수 있는 문제였다.

일단 문제에서 요구하는 손익분기점을 넘기려면, 어떤 지점에서 판매량과 총 제작비용이 같아지는지 알아야한다. 즉 아래와 같은 방정식을 세울 수 있다. 

고정 비용 (a) + 가변 비용 (b) * 판매 수 (x) = 판매 비용 (c) * 판매 수 (x)

a + bx = cx

a = (c - b)x

a / (c - b) = x

따라서 고정 비용을 판매 액에 가변 비용을 뺀 값으로 나눈 값이 제작에 든 비용을 전부 매꾸는데 판 제품의 개수이다. 즉 손익분기점을 넘기려면 이 지점에서 1대 더 팔아야 하므로 x + 1, 즉 a / (c - b) + 1 을 해준 값이 답이 된다.

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <string>

using namespace std;

long long a, b, c;

void check(){

    long long left = 0;
    long long right = 2100000000; 

    while(left <= right){
        long long mid = (left + right) / 2;
        if(a + b * mid < c * mid){
            if(a + b * (mid - 1) >= c * (mid - 1)){
                cout << mid; return;
            }
            right = mid - 1;
        }
        else if(a + b * mid > c * mid){
            left = mid + 1;
        }

        else{
            cout << mid + 1; return;
        }
    }
}

void check2(){
    cout << a / (c - b) + 1;
}

int main(){
    
    ios::sync_with_stdio(false);
	cin.tie(NULL);
    cout.tie(NULL);

    cin >> a >> b >> c;

    if(b >= c) { cout << -1; return 0; }

    check2();

    return 0;
}