문제

문제 설명

상근이는 여자친구를 데리러 가야 한다. 상근이의 차에는 기름이 t만큼 있고, 여자친구는 상근이가 현재 있는 위치와 m킬로미터 떨어져 있다.

상근이는 여자친구를 최대한 빨리 데리러 가야 하기 때문에, 중간에 주유소에 들릴 시간이 없다. 어렸을 때부터 물리, 수학 영재로 전국에 이름을 날리던 상근이는 차의 속도에 따라 소모되는 기름의 양을 계산했다.

속도가 시속 v 킬로미터 일 때, 한시간 동안 소모되는 기름의 양은 다음과 같다.

av4 + bv3 + cv2 + dv

상근이는 출발할 때부터 도착할 때까지 일정한 속도로 이동한다. 기름이 바닥나지 않으면서 최대한 여자친구에게 빨리가려면 시속 몇 킬로미터로 이동해야 하는지 출력한다.

---

Python

import math
from sys import stdin

def calculate(a, b, c, d, v, m):
    return m/v*(a*v**4 + b*v**3 + c*v**2 + d*v)

while True:
    try:
        a, b, c, d, m, t=map(float, stdin.readline().strip().split())
        start=1
        end=1000000000
        answer=0

        for _ in range(100):
            mid=(start+end)/2
            if calculate(a, b, c, d, mid, m)>t:
                end=mid
            else:
                start=mid
                answer=mid

        print("%0.2f" % (math.floor(answer*100)/100))
    except:
        break

Java

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

public class Main {
    public static double fuel(double a, double b, double c, double d, double m, double v) {
        return m*(a * Math.pow(v, 3) + b * Math.pow(v, 2) + c * Math.pow(v, 1) + d);
    }

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

        while (true) {
            try {
                StringTokenizer st = new StringTokenizer(br.readLine());
                double a = Double.parseDouble(st.nextToken());
                double b = Double.parseDouble(st.nextToken());
                double c = Double.parseDouble(st.nextToken());
                double d = Double.parseDouble(st.nextToken());
                double m = Double.parseDouble(st.nextToken());
                double t = Double.parseDouble(st.nextToken());

                double start = 1;
                double end = 1000000000;
                double answer = 0;

                int range=400;
                while (range-->0) {
                    double mid = (start + end) / 2;

                    if (t < fuel(a, b, c, d, m, mid))
                        end = mid;
                    else {
                        answer = mid;
                        start = mid;
                    }
                }

                bw.write(String.format("%.2f", (int) (answer * 100) / 100f) + "\n");
                bw.flush();
            } catch (Exception ignored) {
                break;
            }
        }
    }
}

---

해결 과정

1. 테스트케이스가 몇 개인지, 또는 입력이 끝나는 조건이 무엇인지 주어지지 않아서 당황했다. 런타임에 Exception이 뜰 것 같았지만 문제 구현부터 시작했다. 단순히 주어진 공식대로 계산해서 속도를 기준으로 Binary Search를 했다.

2. 틀렸습니다! 나는 Binary Search를 쓸 때마다 정수를 다뤘기 때문에 단순히 start=mid+1 등의 방법으로 범위를 바꿔줬다. 하지만 이번은 Double형이기 때문에 틀렸다. 그래서 start=mid+0.001로 해줬는데 이 또한 더 높은 소수점 자리에서 정답이 있을 수 있기 때문에 또 틀렸다. start=mid로 해두고 mid를 소수점 둘째자리까지 표시했을 때 연속해서 똑같은 mid값이 나오면 break 해줬다. 이 또한 더 높은 소수점 자리에서 둘째 자리까지 영향을 줄 수 있어서 틀렸다...

3. 결국 답을 보고 while문의 반복 횟수를 fix하는 것을 봤다. 이것도 그 값이 너무 크면 비효율적이고 적으면 정확도가 떨어질 텐데 100번 반복일 때는 성공한다. 약 log(2) n=100 이므로 정수 범위에서 10^30 크기까지 되는데 대략 소수점 20자리까지는 정확하게 처리할 것 같다고 생각된다.

4. 😁