[Java] 백준 1712번

Input-1
1000 70 170
Output-1
11

Input-2
3 2 1
Output-2
-1

Input-3
2100000000 9 10
Output-3
2100000001

문제 풀이

이 문제에서 중요하게 봐야할 핵심은 아래와 같다.

• 주어진 수가 21억 이하의 자연수이기에 int형을 사용하면 안된다.
• 손익분기점이 존재하지 않으면 -1를 출력한다.
• 실행 속도가 0.35초 이내여야 한다.

먼저 int형의 경우 -2,147,483,648 ~ 2,147,438,647이기 때문에 이 문제에서 사용 가능한 범위가 아니다.
int형보다 큰 범위를 가지는 long형을 사용해야 한다.

• long은 (-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807)의 범위의 자연수 활용이 가능하다.

그리고 손익분기점이 존재여부를 어떻게 측정할까?
계산해보면 C-B의 값이 0보다 커야 손익분기점이 존재한다.
쉽게 말하면 C의 배수의 값이 B의 배수의 값보다 커야 배수가 높아지면서 C가 B를 넘어설 수 있기 때문이다.

코드로 작성해보면 아래와 같다.

if(B >= C) bep = -1;
else {
    // 손익분기점이 존재할 경우
}

또한 실행속도가 0.35초 이내여야 하는데 처음에는 while문 에서 A+B반복횟수(총 수입)이 C반복횟수(총 수입)보다
작을 경우 bep(손익분기점=반복횟수)를 증가시키고, 클 경우에는 반복문을 탈출하도록 작성하였다.
그런데 시간초과가 발생하였다.

반복문 내에서 반복횟수별로 카운트를 증가시키는 방식으로 접근하니 시간이 초과된 것 같다.

반복문으로 작성한 코드

if(B >= C) bep = -1;
else {
    while((A+B*bep) >= (C*bep)) { // 총 수입이 총 비용보다 높을 경우
        bep++;
    }
}

그렇다면 어떻게 시간을 줄일 수 있을까?
아예 방정식같은 느낌으로 한번에 bep(손익분기점) 값을 측정해야겠다고 생각했다.

A+C-B의 값을 C-B의 값으로 나누니 원하는 값을 얻을 수 있었고 시간도 대폭 줄일 수 있었다.
해당 식을 적용한 코드는 아래와 같다.

식으로 작성한 코드

if(B>=C) bep = -1;
else bep = (A+C-B) / (C-B);

작성코드

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));                
        StringTokenizer st = new StringTokenizer(br.readLine());

        long A = Integer.parseInt(st.nextToken());
        long B = Integer.parseInt(st.nextToken());
        long C = Integer.parseInt(st.nextToken());
        long bep = 1;
        
        if(B>=C) bep = -1;
        else bep = (A+C-B) / (C-B);

        bw.write(bep + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

회고

• 특정 반복문 내에서 횟수별로 검증하는 것은 적은 시간을 요구하는 문제에서는 올바른 접근이 아니라는 것을 알게 되었다.
• 특정 패턴 및 로직을 하나의 식으로 표현함으로 실행 속도 시간을 대폭 줄일 수 있었다.