[백준/C++] 집으로 (No. 1069)

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 단순히 거리를 계산하면 쉽게 풀 수 있는 문제다.

 

먼저 점프해서 이동하는 이동거리 D를 이동 시간 T로 나눈 값이 1보다 작다면 걸어가는 것 보다 느리기 때문에 점프를 이용할 이유가 없다.

 

반대로 점프할 경우가 이득이라면 3가지 방법으로 나눌 수 있다.

 

그전에 n은 (0, 0)에서 목적지인 A 점 까지의 이동거리를 D로 나눈 값이다.

여기서 n을 계산하는 이유는 A점까지 n번 점프하고 남은 거리를 걸어가는 방법을 계산하기 위해서다.

 

1. (0, 0)에서 직선거리로 점프를 n번 한 다음 걸어서 목적지인 A지점에 도착한다.

2. (0, 0)에서 직선거리로 점프를 n+1번 한 다음 반대로 걸어서 A지점에 도착한다.

3. (0, 0)에서 n+1번 한 다음 목적지인 A지점에 도착한다.

 

여기서 2번 방법은 n이 0인 경우에만 고려하면 된다.

 

아래 그림을 통해 n>0인 경우, n=0 인경우를 보면 이해가 쉽다.

​

 

[아이디어 정리]

1. 점프를 하는게 걸어가는 것 보다 빠른 경우에 점프를 해 이동하는 방법을 고려한다.
2. (0, 0)에서 A점까지 거리를 점프 할 경우 이동거리 D로 나눈 값을 n이라고 할 때, n=0인 경우와 n>0인 경우로 나눈다.
3. n=0인 경우 T * 2, T + 걷기, 그냥 걷기의 경우 중 최솟값을 구한다.
4. n>0인 경우 T * (n+1), T * n + 걷기의 경우 중 최솟값을 구한다.

 

 

Code

 

 

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	double X, Y, D, T, Dist;
	cin >> X >> Y >> D >> T; // T초에 D만큼
	Dist = pow(X * X + Y * Y, 0.5);
	
	cout << fixed;
	cout.precision(16);
	if (D / T > 1) {
		int n = Dist / D;
		double f1 = Dist - n * D + n * T;
        double f2;
        if (n<=1){
            f2 = min(2*T, abs(Dist - (n + 1) * D) + (n + 1) * T);
        }
        else{
            f2 = (n + 1) * T;
        }
		cout << min({ f1, f2 })<<"\n";
	}
	else {
		cout << Dist;
	}

	return 0;
}

 

---

점프를 할 경우가 이득일 때, 어떤 방법이 있는지 고려하면 쉽게 풀 수 있는 문제다.

 

https://www.acmicpc.net/submit/1069/79746145