[C++]백준 - 1069번 문제

1069번: 집으로 (acmicpc.net)

1069번: 집으로

 

1069번 : 집으로

---

은진이는 지금 (X, Y)에 있고, (0, 0)에 있는 집으로 가능한 빨리 가려고 한다. 이동할 수 있는 방법은 다음 두 가지이다.

첫 번째 방법은 걷는것이다. 걸을 때는 1초에 1만큼 움직인다. 두 번째 방법은 점프하는 것이다. 점프를 하게 되면, T초에 D만큼 움직인다. 점프는 일직선으로만 할 수 있고, 정확하게 D칸만 움직일 수 있다.

위의 두 가지 방법을 이용해서 집에 돌아오는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오. 꼭 한 가지 방법만 사용해야 되는것이 아니고, 두 가지 방법을 적절히 조합해서 가장 빠른 시간을 구하는 것이다.

 

입력

---

첫째 줄에 네 정수 X, Y, D, T가 주어진다.

• 1 ≤ X, Y ≤ 1,000
• 1 ≤ D, T ≤ 10,000

 

출력

---

첫째 줄에 집에 돌아오는데 걸리는 시간의 최솟값을 출력한다. 절대/상대 오차는 10-9까지 허용한다.

 

 

---

 

생각해 볼 점

---

그냥 구현문제입니다.

 

걸어갈 경우, 거리와 같은 시간이 걸릴 것이고,

점프를 할 경우, 조금 복잡합니다.

 

조건을 몇개 설정해봅시다.

 

1. 걸어가는 것보다 점프의 효율이 낮다. 

 

-> 그냥 distance를 구해서 출력합니다.

 

2. distance가 점프 거리 * 2보다 길다.

 

-> (0, 0) 방향으로 점프를 여러번 해서, distance <= 점프거리 * 2로 만듭니다. 

 

3. 계산을 통해 경우의 수를 나눕니다.

 

3-1. 남은 거리 걸어가기

 

-> 이 경우는 애초에 있을 수 없습니다.

 

앞에서 점프 효율이 낮은 경우를 걸렀으므로, 걸어가는 경우는 없습니다.

 

3-2. 점프 1회, 나머지 거리는 걷기

 

이 때, 점프 후 역방향으로 걸어오는 것도 포함해야합니다.

이를 포함하기 위해, distance - jump를 수행할 때에는 절댓값을 붙입니다.

 

 

3-3. 2번 점프해서 도달하기

 

 

코드

---

#include <iostream>
#include <cmath>
using namespace std;

inline double get_distance(int const x, int const y)
{
	return sqrt(x * x + y * y);
}

int main()
{
	int X, Y, D, T;
	scanf("%d %d %d %d", &X, &Y, &D, &T);

	double d = get_distance(X, Y);

	double timed = 0.0f;

	//점프가 무의미
	if (T >= D)
	{
		printf("%.10lf", d);
		return 0;
	}

	//목표로 직선 이동
	while (d > 2 * D)
	{
		timed += T;
		d = d - D;
	}
	//점프 2회 혹은 점프 1 + 걷기 중 더 적은 값을 계산
	double cal_time = min(double(2 * T), T + abs(d - D));
	if (d > cal_time)
	{
		timed += cal_time;
		d = 0;
	}
	//걸어가는 것이 이득
	timed += d;
	printf("%.10lf", timed);
	return 0;
}

 

그 외

---