[백준] 1069번 - 집으로 (Gold 3)

문제 링크

[백준] 1069번 - 집으로 (Gold 3)

문제 설명

(X, Y)에서 (0, 0)까지 이동하려고 한다.
이동할 수 있는 방법은 두가지가 있는데, 1초에 1만큼씩 걷는 것과 T초에 D만큼 점프하는 것이다.
점프하는 경우 정확히 D만큼의 거리만 움직일 수 있으며, 일직선으로만 점프가 가능하다.
이동하는데 걸리는 최소 시간을 구하시오.

정답 코드 및 설명

경우의 수를 아래와 같이 나누어서 생각하자.

1. $D \leq T$ : 점프하는 것이 걷는 것보다 속도가 느리다.
   • (X, Y)에서 (0, 0)까지 걷는 것이 가장 빠르다.
   • 이동시간은 $\sqrt{X^2 + Y^2}$
2. $D > T$ : 점프하는 것이 걷는 것보다 빠르다.
   • 가급적이면 점프로 많은 거리를 이동하고, 남은 거리를 걷는 것이 빠르다.
   • (X, Y)부터 (0, 0)까지의 거리 $d = \sqrt{X^2 + Y^2}$
   • N = $d$를 D로 나눈 몫
   • Case 2-1 : N = 0
     • 점프를 두 번 해서 도착하는 경우 : 이동시간 $2T$
     • 점프를 한번 하고 남은 거리를 되돌아오는 경우 : 이동시간 $T+D-d$
     • 걸어가는 경우 : 이동시간 $d$
     • 세 경우 중 가장 이동시간이 짧은 경우를 택하면 된다.
   • Case 2-2 : $N \geq 1$
     • (N+1)번 점프해서 도착하는 경우 : 이동시간 $(N+1)T$
     • N번 점프하고 남은 거리를 걸어가는 경우 : 이동시간 $NT + d - ND$
     • 두 경우 중 이동시간이 짧은 경우를 택한다.

N이 1 이상이라면 (N+1)번의 점프로 정확히 원점에 도착할 수 있지만, N이 0이라면 아닐 수도 있기 때문에 Case 2-1과 Case 2-2를 분리해서 생각해야 한다.
이를 코드로 구현하면 아래와 같다.

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

public class BOJ1069 {
    int x, y, d, t;

    double distFromOrigin() {
        return Math.sqrt(x * x + y * y);
    }

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        x = Integer.parseInt(st.nextToken());
        y = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        t = Integer.parseInt(st.nextToken());
    }

    double time() {
        double dist = distFromOrigin();
        if (t >= d) return dist;
        int jump = (int) Math.floor(dist / d);
        double time;
        if (jump == 0) {
            time = t + (d - dist);
            if (2 * t < time) time = 2 * t;
            if (dist < time) time = dist;
            return time;
        }
        time = t * jump + (dist - d * jump);
        if (t * (jump + 1) < time)
            time = t * (jump + 1);
        return time;
    }

    void solution() throws IOException {
        input();
        System.out.println(time());
    }

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