[자바] 백준 14786 - Ax+Bsin(x)=C ② (java)

목차

문제 : boj14786

 

 

필요 알고리즘

• 수학, 이분 탐색
  
  • 이분 탐색으로 답의 범위를 좁혀가며 상대 오차 10^-9 이하로 찾아주면 된다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  처음에 문제보고 일단 수식이 나오니 무서웠는데, 어차피 y=x랑 y=sin(x) 합친 형태라 대충 그래프 형태가 상상이 되기도 하고, 입력값 범위도 좁아서 도전해보니 생각보다 어렵진 않았다.

 

  풀고보니 '뉴턴-랩슨법' 이라는걸로 풀면 바로 풀린다고 한다..

 

 

  내 경우엔 좀 무식하게 풀었다. 우선 그래프 모양은 아래처럼 생겼다. 결국 저게 y=C인 지점의 x값이 답이 될꺼다. y=Ax는 그냥 오른쪽위로 쭉 뻗는 직선, y=Bsin(x)는 [-B, B] 범위에서 물결을 그리는 형태이다. 이 때, B<=A 라고 조건이 주어졌으므로 아래처럼 다시 감소하는 부분이 없는 그래프가 그려지게 된다.

 

  일단 내 수학적 지식으로는 이걸 한방에 답을 구할 공식같은건 생각이 안났다. 그러니 우선 x의 가능한 범위를 생각해봤다. 얼마 안되면 대충 넣어서 찾아볼 생각이었다. 대강 A, B, C는 [1, 100000] 이므로 가능한 x값은 대략 [-100000, 200000] 정도로 예상했다. 간단히 예를들어 A=1, B=10, C=10 정도라면, x 그래프는 그냥 일직선으로 올라가고, 10sin(x)은 [-10, 10] 사이에서 왔다리갔다리 할테고, 그게 y=10이 되려면 대충 x가 20일 때 10sin(x)가 -10이 되서 딱 y=10이 될 수 있을거라 생각한거고, 그래서 최대 20만이다. C값은 1이 최소이니 대충 최소 -10만으로 잡았다.

 

  아무튼 [-10만, 20만] 범위 정도라면 정수라면 그냥 다 넣어봐도 딱히 문제는 없다. 문제는 x가 실수라는 점인데, 그래서 이분 탐색으로 범위를 좁히기로 했다. 몇 번 정도 범위를 좁히면 될까 생각해봤는데 어차피 저 수식 계산 자체는 O(1) 이므로 뭐 100번정도 해봐도 전혀 문제가 없을꺼라 생각됬다. 총 30만정도의 범위를 2^100 정도의 구간으로 나눈다면, 10^-9 정확도는 충분히 가능할꺼라 판단되어 이분 탐색을 그냥 100번 진행하고 답을 출력하도록 했다.

 

  아 그리고 실수라서 이분 탐색으로 정확히 답이 0이 나오는걸 찾은게 아니다. 현재 보고 있는 범위가 [s, e] 라고 할 때 그 중간값이 m을 잡는다. 그리고 답이 [s, m]과 [m, e] 중 어느 구간에 있는지를 확인한거다. 이건 예를들어 Ax+Bsin(x)-C 수식에다가 s를 넣었을 때 부호가 '+'이고, m을 넣었을 때 부호가 '-' 라면 그 사이에 답이 '0'인게 있다는걸로 판단했다. 

 

  이 과정은 아래 그림에서 초록 -> 파랑 -> 주황 -> 빨강 처럼 점점 답이 포함되는 범위를 좁혀나가는 과정이다. 이걸 100번 진행했으므로, 정확도가 점점 높아진다.

 

 

  세세하게 따져본게 아니라, 어차피 입력값이 작고 시간 복잡도상으로 여유가 많으니 대~충 범위들을 설정하고 틀리면 다시 설정하려고 했는데, 한방에 통과되었고 시간도 충분해서 별 문제없이 통과됬다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private int a, b, c;

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        double s = -100000;
        double e = 200000;

        int n = 100;
        while (n-->0) {
            double m = (s+e)/2;
            if (isPositive(s) != isPositive(m)) e = m;
            else s = m;
        }
        System.out.println(s);
    }

    private boolean isPositive(double x) {
        return a*x + b*Math.sin(x) - c >= 0;
    }
}