백준 17236번 Python / 수학, 이진(이분)탐색(Binary Search)

문제풀이 GitHub

https://github.com/Seokii/baekjoon

GitHub - Seokii/baekjoon: Daily Commit for Baekjoon

문제링크

https://www.acmicpc.net/problem/17236

17236번: Heights

이진탐색이란?

https://seokii.tistory.com/106

[알고리즘] 이진 탐색(Binary Search)이란?

 

풀이

import math
h1 = float(input())
h2 = float(input())
h3 = float(input())

def heron(a,b,c):
    s = (a+b+c) / 2
    return math.sqrt(s * (s-a)*(s-b)*(s-c))

def judge(s):
    a = 2.0 * s / h1
    b = 2.0 * s / h2
    c = 2.0 * s / h3
    k = heron(a,b,c)
    differ = abs(s-k)
    if differ < 0.000001: return 0
    elif s > k: return 1
    else: return 2

answer = 0
left = 0
# right = float('inf')
right = 123456789.0
while (left < right):
    mid = (left+right) / 2
    tmp = judge(mid)
    if tmp == 0:
        answer = mid
        break
    elif tmp == 1: left = mid
    else: right = mid

print(answer)

삼각형 세 변의 길이를 각각 a, b, c라고 할 때 각 변에 대한 삼각형의 넓이는 다음과 같습니다.

a의 넓이 = 1/2 * a * a의 변에서 그어지는 높이
b의 넓이 = 1/2 * b * b의 변에서 그어지는 높이
c의 넓이 = 1/2 * c * c의 변에서 그어지는 높이

 

이를 각각 a, b, c로 나타내면 다음과 같습니다.

a = 2 * a의 넓이 / a의 변에서 그어지는 높이
b = 2 * b의 넓이 / b의 변에서 그어지는 높이
c = 2 * c의 넓이 / c의  d변에서 그어지는 높이

 

세 변의 길이를 안다면 헤론의 공식을 통해 삼각형의 넓이를 구할 수 있습니다.

 

heron 함수는 헤론의 공식을 적용한 함수입니다.

judge 함수는 추정하는 넓이 값을 통해 각 변의 길이를 구하고 다시 헤론의 공식으로 삼각형의 넓이를 구합니다. 그 후, 처음 추정하는 넓이와 그 이후 헤론의 공식을 통해 나온 넓이를 비교합니다.

 

위의 두 함수를 통해 처음 추정하는 넓이와 그 후 헤론의 공식을 통해 나온 넓이가 같아질 때까지 값을 조정하며 이진 탐색을 수행하는 것이 정답을 찾는 원리입니다.