백준 10473 인간 대포

문제 URL : https://www.acmicpc.net/problem/10473

10473번: 인간 대포

문제 접근법 : 

문제를 이해하는데 한참 걸린 문제였습니다. 

핵심은 다익스트를 이용하지만 어떻게 배열을 통해서 이용해야하고 n이 100밖에 안되기때문에

전체 다돌려도 충분히 배열안에서 돌릴수있습니다. 

 

첫번째 : 걷는 속도로 갔을때의 시간을 구합니다. 이것은 두점 사이의거리를 이용해서 구할수있습니다. 피타고라스의 법칙이기 때문에 중학교 수학 정도만 끝내도 충분히 알거라 생각합니다.  거리를 구했다면 

시간= 거리/속력 이기때문에 거리/5 해주면됩니다. 

 

두번재 : 로켓을 발사해서 가는 거리인데 결국엔 타고 발사할때 추가로 2초가 걸리고 발사해서 50m까지 가고 다른지점까지 걸어서 갈수있기때문에 원래 현재점과 다음지점사이의 거리에서 -50m를 해주면 거리가 나옵니다. 시간을 구해야하기 때문에 그거리값에서 당연히 5를 나눠주고.

여기서 중요한건50m를 마이너스 해줬기에 음수가 되면안되기때문에 절댓값을 이용합니다.

 

세번째 : 이게 제일 주용했습니다. 왜자꾸 틀렸는지 이해를 못했었는데 잘생각해보면 처음위치는 발사할수있는 대포자리가 아니기때문에 무조건 걸어서 가야합니다. 그리고 2번째 이동할때는대포를 탈수 있겠지요 이게 핵심이고 엄청 해맸던 조건이였네요

 

이3가지만 만족하면 문제는 풀릴겁니다.

소스코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81

//By 콩순이냉장고 #include<iostream> #include<string> #include<algorithm> #include <vector> #include <queue> #include <cmath> using namespace std; typedef pair<double, double> P; vector<P> v; int n; double dist[200]; double distance(P a1, P a2){     return sqrt(pow(a1.first - a2.first, 2) + pow(a1.second - a2.second, 2)); } void input() {     double sx, sy, fx, fy;     cin >> sx >> sy;     cin >> fx >> fy;     cin >> n;     v.resize(n + 2);     v[0] = { sx, sy };     for (int i = 1; i <= n; i++)         cin >> v[i].first >> v[i].second;     v[n + 1] = { fx, fy }; } struct Point{     double x, y, time;     Point(double x, double y, double time) :x(x), y(y), time(time){} }; struct cmp{     bool operator()(Point &a, Point &b){         if (a.time>b.time)             return true;         return false;     } }; double dijkstra(){     priority_queue<Point, vector<Point>, cmp> pq;     pq.push({ v[0].first, v[0].second, 0 });     bool first = true;//처음 움직이는거냐 대포를 탈수없음     while (!pq.empty())     {         double curx = pq.top().x;         double cury = pq.top().y;         double time = pq.top().time;         pq.pop();         for (int i = 1; i < v.size(); i++)         {             double walktime = distance({ curx, cury }, v[i]) / 5.0;//걸어서간 시간             double rokettime = 2 + abs(distance({ curx, cury }, v[i]) - 50) / 5.0;//로켓을 이용한시간             double mintime = min(walktime, rokettime);//둘중에 작은걸로             if (first)//처음움직인거라면 대포를 탈수없음 무조건 걸어서가야함                 mintime = walktime;             if (dist[i]>(time + mintime)){                 dist[i] = time + mintime;                 pq.push({ v[i].first, v[i].second, dist[i] });             }         }         first = false;//한번 움직였다면 다음부터는 대포를 이용가능 핵심입니다.     }     return dist[n + 1]; } void solve() {     for (int i = 0; i <= 150; i++)         dist[i] = 1e+9;     cout << dijkstra() << "\n";   } int main(void) {     ios_base::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);     input();     solve(); }     Colored by Color Scripter

cs

궁금한점 혹은 모르는점 , 혹은 제가 무엇인가 틀린것이있다면 언제든 댓글을 이용해주시길 부탁드립니다.