[백준 1712] 손익분기점

 

1. 문제

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

1712번: 손익분기점

 

2. 설계도

 

3. Flowchart

 

실패다.

 

이 순서도는 정답은 도출하나 시간복잡도에서 털렸다.

 

4. 핵심 전략

수식 세우기

A + BN < CN 을 만족하는 min(N) 값 구하기.

 

5. Mistake

 

(1) data range

while문 사용시

수의 범위 int형으로 안되고 long long int ..

아 ..이거때메 실패가 몇번이 뜬건지..

 

(2) 반복문 풀이시 시간초과

=> 수식 변형이 필요함

 

EA + BN < CN
=>A < (B-C)N
=> A / (B-C) < N  // 이 식을 만족하는 최소값 N을 구해야함.

∵ N을 반복문에 때려서 하나씩 증가시키는 for, while loop은 연산량이 많다.

 

 

A/(B-C) == 손익분기점 판매개수

를 계산한 값에 +1 해주면된다.

(∵ 나누어 떨어지는 수 == '손익분기점' 도달 포인트

문제에서 요구하는 답은 손익분기점을 '넘는' 개수 => +1)

 

=> 수식변형 A/(B-C) == 손익분기점 판매개수 

이 식을 이용할 경우 모든 변수를

long long 필요없이 int로 해도 올바른 답이 나온다.

 

 

6. 소스코드

 

[시간 초과 답안] (while문 풀이)

#include <iostream>
using namespace std;
 
int get_break_end_Point(long long int initial_cost,long long int variable_cost,long long int price){
    if(variable_cost >= price)
    return -1;
    else{
        int N = 0; 
        int res = initial_cost + (variable_cost - price) * N;
        //수의 범위가 억대를 넘나들기 때문에 while문 풀이시 시간초과
            while(res >= 0){
            res = initial_cost + (variable_cost - price) * N;
             N++;    
            }
 
        return N;
 
    }
    
}
int main(void){
    long long int A, B, C;
    long long int result;
    
    cin >> A >> B >> C;
    result = get_break_end_Point(A, B, C);
    cout << result; 
    
    return 0;
}

 

 

[올바른 답안]

#include <iostream>
using namespace std;
 
long long int get_break_end_Point(long long int initial_cost,long long int variable_cost,long long int price){
    if(variable_cost >= price)
    return -1;
    else{
        //initial_cost + variable_cost * N < price * N을 만족하는 N이 정답 
        // 식 변형 
        // initial_cost< (price - variable_cost) * N
        // initial_cost / (price - variable_cost) < N;
 
        long long int N = initial_cost / (price - variable_cost) + 1;
        // 딱 떨어진 수보다 + 1 
        return N;
    }
    
}
int main(void){
    long long int A, B, C;
    long long int result;
    
    cin >> A >> B >> C;
    result = get_break_end_Point(A, B, C);
    cout << result; 
    
    return 0;
}

 

 

[int형 모범 답안]

#include <iostream>
using namespace std;
 
int get_break_end_Point(int initial_cost, int variable_cost, int price){
    if(variable_cost >= price)
    return -1;
    else{
    int N = initial_cost / (price - variable_cost) + 1;
        // 딱 떨어진 수보다 + 1 
        return N;
    }
    
}
int main(void){
    int A, B, C;
    int result;
    
    cin >> A >> B >> C;
    result = get_break_end_Point(A, B, C);
    cout << result; 
    
    return 0;
}

 

 

시간 복잡도를 맞춰주기 위해 식(알고리즘)을 변형하면

수의 범위가 21억이므로 int형으로만 계산해도 올바른 답 도출.