[자바] 백준 2734 - 드럼통 쌓기 (java)

목차

문제 : boj2734

 

 

필요 알고리즘

• 기하학
  
  • 기하학 문제이다... 수학 어렵다.

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

 

 

풀이

  입력으로 쓰레기통의 가장 아래에 있는 N개의 드럼통이 주어진다. 그리고 항상 그 윗줄에는 N-1개의 드럼통이 있다고 했고, 그런식으로 위로 쌓다가 가장 위 1개의 드럼통의 (x,y)를 구하는 문제이다.

 

  그래서 풀이자체는 간단한데, N개의 입력이 주어지면 최종적으로 남은게 1개일 때 까지 다음을 반복한다.

1. 현재 가지고 있는 X개의 드럼통을 인접한 2개씩 보면서, (최초엔 X = N)

2. 두 드럼통과 인접하면서 그 위에 쌓이는 한개의 드럼통의 중심좌표를 구한다. 이러면 X-1개의 결과가 나온다

3. X가 1일 때 까지 반복한다.

 

  이하 코드 부분에서 arr이 X개의 드럼통을 가지고 있는거라고 보면 된다. arr에서 인접한 2개를 꺼내서 계산시키고, tmp에 담는다. 이 경우 arr.size()-1 만큼이 tmp의 size가 될꺼다. 그리고 arr을 tmp로 바꿔서 다음번 로직을 돌리고, 이걸 arr.size()가 1이 되면 멈춘다.

while (arr.size() > 1) {
    List<double[]> tmp = new ArrayList<>();

    for (int i = 1; i < arr.size(); i++) {
        tmp.add(calc(arr.get(i-1), arr.get(i)));
    }
    arr = tmp;
}

 

 

  근데 위의 로직은 뭐 간단하다. 다만 기하학 문제라 말로는 쉽지만, 두 원에 인접한 원의 중심좌표를 구하는게 수학이 약한 내겐 어려웠다. calc 함수가 해당 역할을 한다.

public double[] calc(double[] p1, double[] p2) {
    double x1 = p1[0]>p2[0]?p2[0]:p1[0];
    double y1 = p1[0]>p2[0]?p2[1]:p1[1];
    double x2 = p1[0]>p2[0]?p1[0]:p2[0];
    double y2 = p1[0]>p2[0]?p1[1]:p2[1];

    double dist = sqrt(sq(x2 - x1)+sq(y2 - y1));

    double xc = (x1 + x2)/2;
    double yc = (y1 + y2)/2;
    double height = sqrt(4 - sq(dist/2));

    double rx = -(y2 - y1)/dist*height;
    double ry = (x2 - x1)/dist*height;

    return new double[] {xc+rx, yc+ry};
}

 

 

  저 calc 함수가 어떻게 나왔는지 설명해보면 이하와 같다. 물론 난 수학에 약하므로 더 쉽고 좋은 방법이 있을 수 있다.

 

A : 두 원의 중심좌표 사이의 거리를 구하는 과정이다.

B : 두 원의 중심좌표들의 중심좌표 (xc, yc)를 구한거다.

C : 새로운 원의 중심좌표는, 'B'와 직교하며 height 만큼 올라간 좌표이다. 피타고라스 써서 height를 구할 수 있다.

D : 두 원의 중심좌표 사이의 벡터 v가 있다. 그리고 그에 직교한 벡터 u가 있다. 구하려는 좌표 (x,y)는 (xc, yc)에서 벡터 v와 직교하는 방향으로 height만큼 진행한거라고 볼 수 있다. 따라서 height만큼 올리기 위해 벡터 u의 단위 벡터를 구하는 과정이다.

E : 최종적으로 벡터 u의 단위 벡터에 height를 곱해준게 rx, ry이다. 그래서 결국 xc+rx, yc+ry 가 답이다. 말로 설명하면, 두 원의 중심 좌표들의 중심점에서 직교하게 height만큼 올라간 좌표를 구한거다.

 

 

코드 : github

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

import static java.lang.Math.*;

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

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

    private void solution() throws Exception {
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (t-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            List<double[]> arr = new ArrayList<>();
            while (n-->0) {
                arr.add(new double[]{Double.parseDouble(st.nextToken()), 1.0});
            }

            while (arr.size() > 1) {
                List<double[]> tmp = new ArrayList<>();

                for (int i = 1; i < arr.size(); i++) {
                    tmp.add(calc(arr.get(i-1), arr.get(i)));
                }
                arr = tmp;
            }

            sb.append(String.format("%.4f %.4f\n", arr.get(0)[0], arr.get(0)[1]));
        }
        System.out.print(sb);
    }

    public double[] calc(double[] p1, double[] p2) {
        double x1 = p1[0]>p2[0]?p2[0]:p1[0];
        double y1 = p1[0]>p2[0]?p2[1]:p1[1];
        double x2 = p1[0]>p2[0]?p1[0]:p2[0];
        double y2 = p1[0]>p2[0]?p1[1]:p2[1];

        double dist = sqrt(sq(x2 - x1)+sq(y2 - y1));

        double xc = (x1 + x2)/2;
        double yc = (y1 + y2)/2;
        double height = sqrt(4 - sq(dist/2));

        double rx = -(y2 - y1)/dist*height;
        double ry = (x2 - x1)/dist*height;

        return new double[] {xc+rx, yc+ry};
    }

    private double sq(double x) {return x*x;}
}