본문 바로가기

개발/알고리즘

백준 2022 사다리 C++ / Java

해당문제를 풀기위해서는 

1) 삼각형의 닮음을 이용하여 C값을 구하는 공식을 도출하고

2) 피타고라스 정리를 이용하여 h1과 h2의 값을 구하는 공식을 도출한다음

3) 이분탐색을 이용하여 문제를 풀어야 한다.

 

삼격형의 닮음을 이용하면 c 값을 구하는 공식이 도출이 된다.

 

구해야하는 길이를 d라고 하면 피타고라스 정리에 의해 다음과 같은 식이 도출 된다.

  • h1 = sqrt(x^2 - d^2)
  • h2 = sqrt(y^2 - d^2)

삼각형의 닮음을 이용하여 C값을 도출하는 공식도 구하였고, h1 과 h2 공식도 구하였다.

그렇다면 어떤값을 이분 탐색해야할까 ?

C 값은 h1 과 h2의 값에 의해 결정이 된다.

h1은 x와 d1의 값에 의해 결정이 되고

h2는 y와 d2의 값에 의해 결정이 된다.

x와 y는 이미 문제에서 고정으로 주어지는 값이기 때문에 d의 값을 이용하여 C를 찾으면 된다.

d와 C는 반비례 관계이다.

 

이 문제는 실수를 다루기 때문에 주의해서 풀어야 한다.

그 동안 이분탐색을 할 때 아래와 같은 구현체로 문제를 풀었는데, 이는 정수 범위내에서만 정답을 도출하였기때문에 가능했다.

while(lo <= high)
{
	int mid = (lo + high) / 2;
	if(check(mid))
    {
    	lo = mid + 1;
    }
    else
    {
    	high = mid - 1;
    }
}

mid - 1, mid + 1 사이에 정답이 있을 수 있기때문에 해당 표현으로는 정답의 범위를 줄여나갈 수 없다.

해당 문제는 소수점 셋째자리까지 출력하라고 되어있기때문에 조금 더 큰 범위로 abs(right - left) > 1e-6 표현을 이용하면 된다.

이는 소수점 6번째자리까지는 같다는 걸 의미하기 때문이다.

 

코드1(C++)

#include <iostream>
#include <cmath>

using namespace std;

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    cout.tie(NULL);

    double x, y, c;
    cin >> x >> y >> c;
    double lo = 0, hi = min(x, y), ans;
    while(abs(hi-lo) > 1e-6)
    {
        double mid = (lo + hi) / 2.0;
        double d = mid;
        double h1 = sqrt(x*x - d*d);
        double h2 = sqrt(y*y - d*d);
        double tempC = (h1*h2)/(h1+h2);
        if(tempC > c)
            lo = mid;
        else
            hi = mid;
    }

    printf("%.3lf\n", lo);
	return 0;
}

 

 

코드2(jave)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double x = sc.nextDouble();
        double y = sc.nextDouble();
        double c = sc.nextDouble();
        
        double lo = 0, hi = Math.min(x, y), ans = 0;
        while(Math.abs(hi - lo) > 1e-6) {
            double mid = (lo + hi) / 2;
            double d = mid;
            double h1 = Math.sqrt(x*x -d*d);
            double h2 = Math.sqrt(y*y -d*d);
            double tempC = (h1 * h2) / (h1 + h2);
            if(tempC > c)
                lo = mid;
            else
                hi = mid;
        }
        System.out.printf("%.3f\n", lo);
    }
}

'개발 > 알고리즘' 카테고리의 다른 글

백준 1520 내리막 길 java  (0) 2021.06.20
백준 구간 나누기2 13397  (0) 2021.06.18
백준 1939 중량제한 C++ /Java  (0) 2021.06.17
백준 1149 RGB거리 C++  (0) 2021.06.03
백준 16118 달빛여우 C++  (0) 2021.05.31