백준 4454 상근이의 여자친구(with Python)

어떤 문제?

제목에 적힌 문제이고, 이분탐색 문제입니다.

테스트 케이스

내가 무엇을 실수하고 잘못 생각했는지 찾기 위해 구글링을 했습니다.
다행히 자료가 나왔고, 사이트를 공유하고자 합니다.
(링크에서 직접 2011년도 H번 문제를 보시면 됩니다. 입출력 데이터 있습니다.)

내가 생각한 Solution

문제에서 생각해볼 점

• 나는 처음에 이분 탐색 문제가 아니라 방정식을 구해서 푸는 문제라고 생각했다.

• 아래 그림은 나의 생각을 표현하고있다.

• 실제로 solver를 이용하면 아래 그림과 같이 정답을 얻을 수 있습니다. (첫번째 케이스 예시, 이용 사이트는 wolframalpha 입니다.)

• 파이썬에서 solver를 활용할 수 없으니(scipy는 가능한 것으로 알고 있지만 내장함수가 아니라서 ㅜ) 결국 위 그림의 내용대로 이분 탐색을 활용하였다.

• v의 값을 찾아야해서 범위를 정하려고 했는데, 시속 1,000 km/h를 넘기진 않을것 같아서 1,000을 최대로 잡고 구현했다.

• 소수점 아래 2번째까지 구하고 버림을 해야 하므로 1,000 km/h를 1,000,000 m/h로 변환하여 구현했다.

• 그리고 처음에는 소수점을 버리라고 해서 아래 그림과 같이 구현했다.

• 하지만 출력결과가 예상과 달랐다.

a = 231.725
print("%.2f"%a) # 출력 231.72, 예상 231.73

a = 0.005
print("%.2f"%a) # 출력 0.01, 예상 0.01

• 자기(Python) 멋대로 반올림을 올리고 내려서, 결국 문자열로 소수점 아래의 숫자들을 처리했다. (어렵지 않아서 코드를 보시면 금방 이해되실 겁니다.)

• 마지막으로 입력의 개수가 미리 주어지지 않아서 언제까지 입력을 받을지 결정해야 하는데, try & except를 활용하면 해당 문제를 해결할 수 있습니다. (구글링 하시면 금방 이해하실겁니다.)

코드 구현

import sys
# sys.stdin = open(r'/Users/kangdaeyoung/Downloads/io/h.in', 'r')

while True:
    try:
        a, b, c, d, m, t = map(float, sys.stdin.readline().split())
        # a, b, c, d, m, t = map(float, '2.52121324021923e-008 6.47515782809261e-006 0.000756462312768102 0.344505272564564 41.40283203125 39.8583984375'.split())
        l, r = 1, 1000000
        while l <= r:
            v = (l+r) // 2
            float_v = v / 1000
            if m*(a*float_v**3 + b*float_v**2 + c*float_v + d) <= t:
                l = v+1
            else:
                r = v-1
                
        str_r = str(r/1000)
        # 소수점 아래 버림을 구현
        tmp = str_r.split('.')
        if len(tmp[-1]) >= 3:
            # 소수점 이하 숫자 개수가 2보다 크면 2번째까지 잘라줍니다.
            tmp[-1] = tmp[-1][:-1]
        elif len(tmp[-1]) <= 1:
            # 소수점 이하 숫자 개수가 2보다 작으면,
            # 0을 붙여서  소수점 이하 숫자 개수가 2가 되도록 만듭니다.
            tmp[-1] = tmp[-1] + '0'*(2-len(tmp[-1]))
        result = '.'.join(tmp)
        print(result)
    except:
        break