[자바] 백준 9206 - 나무 말고 꽃 (java)

 

 

문제 : boj9206

---

 

필요 알고리즘 개념

• 수학, 미적분학, 수치해석
  
  • 정적분을 통해 풀 수 있는 문제이다. 추가로 적분값의 근사치를 알 수 있는 심프슨 공식 등도 필요하다.

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

 

---

 

풀이

  우선 문제부터 이해해보자.

꽃병의 윤곽은 $f(x)=a\bullet e^{-x^2}+b\bullet \sqrt{x}$ 이고, x축에 대해서 회전시킨 모양이라고 한다.

예를들어 a=1.0, b=2.0 일 경우 윤곽 그래프는 다음과 같다.

 

  h=2.0 이라면 이걸 x축을 기준으로 회전시키면 아래처럼 될 것이다. (h는 x=0부터 x=h 까지를 뜻한다)

 

  그럼 부피는 $\int_{0}^{h}f(x)^{2}\pi \mathrm{dx}$ 와 같이 될 것이다.

저대로 적분해서 풀 수가 없으므로 일정 구간으로 나누어서 정적분 계산을 해준다.

처음엔 사다리꼴 공식(위키)으로 근사치를 구하려 했는데 실패했고, 결론적으로 심프슨 공식(위키)으로 성공했다.

  위 위키에 나와있는 공식대로 구현해주면 된다.

이 문제에서 제시된 $f(x)=a\bullet e^{-x^2}+b\bullet \sqrt{x}$ 인데, 당연히 이걸 그대로 넣으면 안되고

위 공식의 f(x)부분에 $f(x)^2\pi$ 을 넣어주면 된다. (코드의 g())

 

  여기서 a와 b는 0부터 h를 적절히 나누어서 합을 구해주면 된다. 내 경우엔 $h/0.00005$ 개의 구간으로 나누어서 계산했다. 즉, x축을 세세하게 나눈 구간의 간격을 interval이라고 할 때 $interval = h/(h/0.00005)$ 이다.

현재 i번째 구간이라 하면, i=0부터 i=구간의 수 까지 i를 증가시키면서 a=i*interval ~ b=(i+1)*interval 사이에 대해 심프슨 공식을 계산해주고, 모든 구간의 결과를 합치면 된다.

double ans = 0.0d;
for (int i = 0; i < numOfInterval; i++) {
    double a = interval*i;	//나뉜 구간의 시작 지점
    double b = interval*(i+1);	//나뉜 구간의 끝 지점
    ans += interval/6*(g(a)+4*g((a+b)/2)+g(b));	// 심프슨 공식대로 구현
}
return ans;

 

  그렇게 각 꽃병의 부피를 구하면, 선영이가 찾는 꽃병의 부피 V와의 차이가 가장 작은 꽃병의 인덱스 번호를 출력해주면 된다.

---

 

코드 : github

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

interface Tags { public static final double X_DIVIDE_GAP = 0.00005d;}

class Vase {
    private double a, b, h, interval;
    private int numOfInterval;

    public Vase(StringTokenizer st) {
        this.a = Double.parseDouble(st.nextToken());
        this.b = Double.parseDouble(st.nextToken());
        this.h = Double.parseDouble(st.nextToken());
        this.numOfInterval = (int) Math.ceil(h/Tags.X_DIVIDE_GAP);
        this.interval = h/numOfInterval;
    }

    private double f(double x) {
        return a*Math.exp(-(x*x))+b*Math.sqrt(x);
    }

    private double g(double x) {
        double fx = f(x);
        return fx*fx*Math.PI;
    }

    public double getVolume() {
        double ans = 0.0d;
        for (int i = 0; i < numOfInterval; i++) {
            double a = interval*i;
            double b = interval*(i+1);
            ans += interval/6*(g(a)+4*g((a+b)/2)+g(b));
        }
        return ans;
    }
}

public class Main {
    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        double v = Double.parseDouble(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        double minGap = Double.MAX_VALUE;
        int answer = 0;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            Vase vase = new Vase(st);
            double gap = Math.abs(vase.getVolume() - v);
            if (gap < minGap) {
                minGap = gap;
                answer = i;
            }
        }
        System.out.println(answer);
    }

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