백준 1069 - 집으로

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

힌트

제목 그대로 집으로 가는 방법은 몇 개가 있을까? 넓은 관점으로 생각해본다.

풀이

다음 그림을 보면 이 문제에 대한 핵심을 쉽게 이해할 수 있다.

 

 

위 그림을 보면 알 수 있듯이, 목표를 향해 일직선으로 가는 것보다 점프를 2번 해서 가는 방법이 더 빠른 경우가 존재할 수 있다.

 

우리는 이 사실을 반영하여 목표로 향하는 최소 시간을 구하기 위해 다음 두 방법을 섞었을 경우를 계산할 것이다.

 

1. 목적지까지 일직선으로 걷기 또는 점프하는 시간

2. 목적지에 도착하기 위해 두 번 점프하는 시간

 

일단 초기해를 피타고라스의 정리로 계산한 두 지점 간의 일직선 거리 $(dx^{2} + dy^{2})^{\frac{1}{2}}$로 설정한다.

 

그런 다음 점프 횟수에 대해 반복문을 돌면서 걷기 대신 점프한 만큼의 시간을 다시 계산한다. 그리고 두 번 점프해서 목적지로 도착할 수 있다면, 걷기 대신 점프 2번 시행한 시간을 계산하여 최소 시간을 구할 수 있다.

 

$X, Y \leq 1000$으로 범위가 충분히 작기 때문에 브루트포스를 사용하여 최적해를 구할 수 있다.

 

정답 코드 - C++

#pragma GCC target("fma,avx,avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
 
#include "bits/stdc++.h"
 
using namespace std;
 
int x, y, d, t;
 
void solve()
{
  cin >> x >> y >> d >> t;
  double ans = 0;
  cout.precision(15);
  cout << fixed;
 
  ans = x * x + y * y;
  ans = sqrt(ans);
  double dist = ans;
 
  for (int i = 0; i <= 2000; i++)
  {
    auto remain = dist;
    remain -= d * i;
    double tmp = t * i;
    ans = min(ans, abs(remain) + tmp);
    if (abs(remain) <= d * 2)
    {
      ans = min(ans, tmp + t * 2);
    }
  }
 
  cout << ans;
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}