[백준/파이썬][Gold V] Growling Gears - 10325

[Gold V] Growling Gears - 10325

문제 링크

성능 요약

메모리: 108384 KB, 시간: 96 ms

분류

수학

제출 일자

2025년 2월 18일 19:48:35

문제 설명

The Best Acceleration Production Company specializes in multi-gear engines. The performance of an engine in a certain gear, measured in the amount of torque produced, is not constant: the amount of torque depends on the RPM of the engine. This relationship can be described using a torque-RPM curve.

The torque-RPM curve of the gears given in the second sample input.
The second gear can produce the highest torque.

For the latest line of engines, the torque-RPM curve of all gears in the engine is a parabola of the form T = -aR² + bR + c, where R is the RPM of the engine, and T is the resulting torque.

Given the parabolas describing all gears in an engine, determine the gear in which the highest torque is produced. The first gear is gear 1, the second gear is gear 2, etc. There will be only one gear that produces the highest torque: all test cases are such that the maximum torque is at least 1 higher than the maximum torque in all the other gears.

입력

On the first line one positive number: the number of test cases, at most 100. After that per test case:

• one line with a single integer n (1 ≤ n ≤ 10): the number of gears in the engine.
• n lines, each with three space-separated integers a, b and c (1 ≤ a, b, c ≤ 10 000): the parameters of the parabola T = -aR² +bR+c describing the torque-RPM curve of each engine.

출력

Per test case:

• one line with a single integer: the gear in which the maximum torque is generated.

풀이

# T = -aR^2 + bR + c    1 <= a,b,c <= 10,000
# 변곡점을 구하는 문제
# a = 양수이기 때문에 (-a = 음수)최대 지점을 구하는 문제.
# 기울기 = -2aR + b
# 변곡점은 기울기가 0
# -2aR + b = 0
# R = b / 2a 지점이 변곡점 => 여기서는 최고점이 될 것이다.
# T = -a * (b / 2a) ^ 2 + b * (b / 2a) + c
# = (- b^2 / 4a) + (b^2 / 2a) + c
# = b^2 / 4a + c
# F(a, b, c) = b^2 / 4a + c

def F(a, b, c) :
    return ((b**2) / (4*a)) + c
def sol_10325() :
    n = int(input())
    torque = [list(map(int, input().split())) for _ in range(n)]
    if n == 1 :
        print(1)
        return

    # ans = 수식의 답
    # gear_num = 몇번째 기어인지
    ans = gear_num = 0

    for i, (a, b, c) in enumerate(torque, 1) :
        if ans < F(a, b, c) :
            ans = F(a, b, c)
            gear_num = i

    print(gear_num)
    return

T = int(input())
for _ in range(T) :
    sol_10325()

주석에도 풀이과정이 포함되어 있다.

1. 우리는 교육과정을 거치면서(어딘지 모르겠음), 변곡점이라는 것을 배웠다. 
2. 그래프의 구배가 변하는 지점. (구배 = 기울기) (+ => -, - => + 로 변하는 것인데 이거도 용어 있었던거 같은데 기억 안남).
3. 음의 2차 함수 이기 때문에 변곡점이 그 함수의 최대 지점임을 알 수 있다. 
4. 그럼 변곡점을 구하는 것이 이 문제의 키포인트

변곡점의 특징은 기울기가 0인 지점이다. 

그럼 우리는 도함수를 구해야 한다. 

$$T = -aR^2 + bR + c$$ 

$$F = -2aR + b$$

도함수 구하는 것은 다들 알거라고 생각하고 넘어가겠다. 쉽게 말해서 (T 변화량/ R 변화량) 이다.

여기서 변곡점의 특징을 살려

$$F = 0 인 지점을 찾아라!$$

$$-2aR + b = 0$$

$$R = \frac{b}{2a}$$

이 지점이 변곡점 => 여기서 최대 지점이 될 것이고

$$T = -a (\frac{b}{2a})^{2} + b \frac{b}{2a} +c $$

$$ T = \frac{b^{2}}{4a} + c $$

저는 마지막 수식을 함수로 만들어서 처리를 하였다. 

enumerate(iterator, number=0)를 넣게 되면 처음부터 시작하는데 idx를 number로 표시할 수 있는 효과가 있다.