글 읽기 - (C++)어디가 잘못되었는지 모르겠습니다..

hantaehee 3년 전 0

판매량을 1에서부터 반복시키면 몇억번 반복되면서 시간초과가 되는걸로 보여서 이진탐색과 유사하게 진행해봤습니다..

그래프를 그려보니 c값이 b값보다 커야만 손익분기점이 나올거 같아서 1차적으로 걸러내고, 나머지는 int형의 최대에서 반으로 계속 쪼개면서 판매량이 어디에 위치해있는지 찾는 알고리즘을 구현해 보려고 했으나 이렇게 해도 시간초과가 나오네요..

아무 값이나 테스트케이스에 넣어도 시간문제가 될만큼 반복시행되지 않고 바로바로 값이 나오는것 같은데 그렇다면 어떤값에서 무한루프가 도는걸까요..?

나름 혼자 해결해보려고 노력하고, 질문게시판을 많이 참고했는데도 해결이 안되어서 답답한 마음에 도움을 요청해봅니다ㅠㅠ

#include <iostream>
#include <climits>
#include <math.h>

using namespace std;

int main() {
    unsigned long int valueA, valueB, valueC;   
    //valueA: 고정비용, valueB: 가변비용, valueC: 판매가격
    int count = 1;                              
    //손익분기점은 check값을 x축, 금액을 y축으로 봤을때 y=bx+a와 y=cx의 교점에서 손익분기점이다. (x<int형최대값)
    double check = INT_MAX / pow(2, count++);   
    //최초 check값은 int형 최대값의 절반에서 시작 (이후에 1/4, 8/1, 1/16... 으로 탐색)

    cin >> valueA;
    cin >> valueB;
    cin >> valueC;

    if (valueC > valueB) {
        while (1) {     
            //bx+a와 cx의 교점을 정수 한칸범위로 탐색
            if (valueC * check < valueA + valueB * check && valueC * (check + 1) > valueA + valueB * (check + 1)) {
                if (valueC * ceil(check) < valueA + valueB * ceil(check)) {
                    //check의 값이 실수이므로 실제값의 정수부분의 값을 모르기 때문에 두가지 경우로 나눠서 출력
                    cout << ceil(check);                                        
                    //check값의 올림값보다 실제값이 작으면 그냥 올림값이 손익분기점
                }
                else {
                    cout << ceil(check) + 1;                                    
                    //check값의 올림값보다 실제값이 크면 올림값+0.x가 실제값이므로 올림값+1이 손익분기점
                }
                return 0;  //반복문에 들어왔다면 손익분기점이 존재하므로 손익분기점을 찾고 메인 리턴
            }
            else if (valueC * check > valueA + valueB * check) {    
                //교점이 현재 check값보다 작은 값에 있으면 check 앞쪽을 이등분해서 탐색
                check = check - INT_MAX / pow(2, count);
            }
            else {
                check = check + INT_MAX / pow(2, count);            
                //교점이 현재 check값보다 큰 값에 있으면 check 뒤쪽을 이등분해서 탐색
            }
            ++count;
        }
    }

    cout << -1;   //c값이 b보다 같거나 작으면 교점이 생길수 없으므로 손익분기점이 없다
    return 0;
}

ghkdiwl 3년 전 0

시간제한이 0.35초고 범위도 A,B,C 모두 21억 대라 이분탐색으로도 시간 부족할거에요.

이문제는 그냥

A + Bx > Cx

A > (C-B)x

x<(C-B)/A 일떄의 x를 구하는거라

결국 답 x = (C-B)/A + 1 과 같습니다.

여기서 C가 B보다 작은경우 예외처리만 해주시면 돼요

6줄 내외로 해결되실거에요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

(C++)어디가 잘못되었는지 모르겠습니다..

hantaehee 3년 전 0

ghkdiwl 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말