집으로 C++ - 백준 1069

정말 풀고 싶었던 문제.

문제 접근

이 문제는 최소 경로로 가는 경우의 수가 여러가지여서

많은 조건 분기를 사용해야했다.

거리를 $dist=sqrt(x^2+y^2)$라 하자

1. 걸어가는 것이 점프 한 것 보다 빠를 때

이 경우는 점프를 하면 오히려 손해이므로 그냥 걸어간다.

318 445 1200 800
546.9451526432975

2. 점프한 거리가 $dist$보다 같거나 클 때

이 경우는 점프 두 번에 도착, 점프 한 번만에 도착, 점프 한 번 하고 걸어서 도착할 수 있다.

3 4 6 3
4.0

10 10 1000 5
10.0

3. 점프를 여러 번 하고 걸어가거나, 점프만 하고 도착하는 경우

이 경우는 점프를 여러 번 해서 거리가 $d$보다 작을 때

두 번 점프해서 도착하거나, 걸어서 도착하는 경우가 있다.

6 8 3 2
7.0

400 300 150 10
40.0

코드는 다음과 같다.

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cout << fixed; cout.precision(10);
    double x,y,d,t;
    cin >> x >> y >> d >> t;
    double dist=sqrt(x*x+y*y),ans=dist,tmp=dist;
    if(dist<t){cout << dist; return 0;}
    if(d>=dist){
        cout << min(ans,min(2*t,t+d-dist));
        return 0;
    }
    double cnt=0;
    if((dist/d)==floor(dist/d)) ans=min(ans,dist/d*t);
    while(1){
        if(tmp<d) break;
        if(1<tmp/d && tmp/d<2) ans=min(ans,min(t*cnt+2*t,t*cnt+tmp));
        tmp-=d;
        cnt++;
        if(tmp==0) break;
    }
    if(tmp!=0){
        ans=min(ans,min(t*cnt+2*t,t*cnt+tmp));
    }
    cout << ans;
    return 0;
}