[백준 / BOJ] 1069번 : 집으로 - JAVA

https://www.acmicpc.net/problem/1069

1069번: 집으로

문제 이해

지금껏 풀었던 대부분의 문제가 배열을 바탕으로 한 칸씩 이동하는 것이었기 때문에 처음 문제를 이해할 때 애를 먹었다. 이 문제에서 '1만큼 움직인다'는 1칸 움직이는 게 아니라 그냥 1 움직이는 것이다. 어느 방향이든 상관 없이.

 

빨리 가는 조건

가장 먼저 알아야 하는 것은 방향에 구애받지 않고 움직인다면, 거리가 D * 2 이하인 경우 점프 두 번으로 무조건 도달할 수 있다는 것이다. 다음 그림처럼 길이 D의 선분 두 개 사이 거리는 최소 0부터 최대 2 * D까지 가능하다.

따라서 다음 조건으로 문제를 풀었다.

1. D가 T보다 작다면 (시간 당 거리가 1이 안된다면) 그냥 걸어가는 것이 빠르다.
2. D가 T보다 크다면
    2 - 1. 총 거리가 D보다 작은 경우 i) 그냥 걷는 시간 과  ii) 두 번의 점프로 도달하는 시간, iii) N + 1번 점프한 뒤 더 나아간 거리를 되돌아오는 시간을 비교한다.
    2 - 2. 총 거리가 D보다 큰 경우 i) 총 거리를 D로 나눈 N 보다 한 번 더 점프하는 시간 과 ii) 그냥 걷는 시간을 비교한다.

그림으로 나타내면 다음고 같다.

전체 코드

// 시간 : 76ms
// 메모리 : 11620KB
public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int X = Integer.parseInt(st.nextToken());
		int Y = Integer.parseInt(st.nextToken());
		
		int D = Integer.parseInt(st.nextToken());
		int T = Integer.parseInt(st.nextToken());
		
		if(D <= T) {
			System.out.println(Math.sqrt(X * X + Y * Y));
		} else {
			double dist = Math.sqrt(X * X + Y * Y);
			
			int N = (int) dist / D;
			
			if(dist - N * D == 0) {
				System.out.println(N * T);
			} else {
				if(N == 0) {
					double two_jump = T + T;
					double only_walk = dist;
					double jump_and_back = T + D - dist;
					
					System.out.println(Math.min(two_jump, Math.min(only_walk, jump_and_back)));
				} else {
					double rest = dist - N * D;
					
					double more_jump = T;
					double only_walk = rest;
					
					System.out.println(Math.min(more_jump, only_walk) + N * T);
				}
			}
		}
	}

}