백준 1069번 집으로

문제

백은진은 지금 (x, y)에 있고, (0, 0)에 있는 집으로 가능한 빨리 가려고 한다. 백은진은 다음과 같이 두 가지 방법으로 움직일 수 있다.

첫 번째 방법은 걷는것이다. 걸을 때는, 1초에 1만큼 움직인다.

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

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

문제풀이

사용한 알고리즘 : 구현

(0) 생각

 2차원인걸 생각합니다.

 예를 들어 한번 점프에 1씩 이동하고 (1,1) 에서 (0,0) 으로 간다고 하였을 때, 2번의 점프로 정확하게 갈 수 있습니다.

 즉, 한번 점프보다 남은 집까지의 거리가 작으면, 꺾어서 2번 점프로 갈 수 있습니다.

(1) 코드 11~12

 일단 그냥 걸어가는 시간을 정답으로 잡아놓습니다.

(2) 코드 13~16

  집까지 도착하기 전 일직선으로 최대 몇 번의 점프를 할 수 있는지 구하고, 이후 남은 거리를 구합니다.

(3) 코드 18~23

 0번의 점프를 할 수 있는 경우,

    1. 일직선으로 1번 점프 후, 지나친 거리를 되돌아 오는 경우

    2. 꺾어서 2번 점프만에 가는 경우

 를 생각해줍니다.

(4) 코드 24~29

 과정 (3)의 경우가 아닌, 일직선으로 점프를 할 수 있는 경우,

    1. 최대 점프 한 후 남은 거리 걸어가는 경우

    2. 최대 점프 + 점프 한번 더 해서 꺾어 가는 경우

 를 생각해줍니다.

	#include <bits/stdc++.h>
	using namespace std;
	int X, Y, D, T;
	int main() {ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> X >> Y >> D >> T;
	double Dist = sqrt((double)(X * X + Y * Y));
	// 일단 그냥 걸어가기
	double ans = Dist;
	// Dist / D 몫 cnt 구하기
	int cnt = Dist / D;
	// 남은거리
	Dist -= cnt * D;
	if (cnt == 0) {
	// 1번 점프 후 더 간 거리 되돌아오기
	ans = min(ans, (double)T + ((double)D - Dist));
	// 꺾어서 2번 점프
	ans = min(ans, 2.0 * (double)T);
	}
	else {
	// cnt번 점프 후 남은 거리 걸어가기
	ans = min(ans, (double)cnt * T + Dist);
	// cnt+1번 점프로 꺾어서 도착
	ans = min(ans, (double)((cnt + 1) * T));
	}
	cout << fixed;
	cout.precision(13);
	cout << ans << '\n';
	return 0;
	}

view raw BOJ 1069.cpp hosted with ❤ by GitHub