경비원


작성일 : 2017-01-18 21:09:45
조회수 : 650



설명

※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.


모서리로만 이동할 수 있기 때문에, 최단거리가 나오는 경우가 몇 가지로 정해져 있습니다.


1) 같은 변에 있는 경우 : 그냥 절댓값을 더합니다.

2) 대칭된 변에 있을 경우(남북 or 동서) : 대칭된 변 이외의 변을 하나 무조건 지나가야 하므로 그 길이를 더하고, 남은 길이 중 짧은 길이를 더합니다.

3) 이외의 경우 : 케이스를 나누어 더해줍니다.


다른 방법도 있을 수 있지만, 그냥 막 풀어도 풀리는 문제기에 노가다로 코딩 하였습니다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;

int r[101][2];
int main()
{
    ios::sync_with_stdio(false);
    int w, h, n, px, py, ans = 0;

    cin >> w >> h >> n;
    for (int i = 0; i < n; i++) cin >> r[i][0] >> r[i][1];
    cin >> px >> py;

    for (int i = 0; i < n; i++)
    {
        int tmp = 0;
        if (r[i][0] == px) tmp += abs(r[i][1] - py);
        else if (r[i][0] + px == 3 || r[i][0] + px == 7)
        {
            if (px < 3)
            {
                tmp += h;
                tmp += min(py + r[i][1], 2 * w - py - r[i][1]);
            }
            else
            {
                tmp += w;
                tmp += min(py + r[i][1], 2 * h - py - r[i][1]);
            }
        }
        else
        {
            if (px == 1)
                tmp = (r[i][0] == 3) ? py + r[i][1] : w - py + r[i][1];
            else if (px == 2)
                tmp = (r[i][0] == 3) ? py + h - r[i][1] : w - py + h - r[i][1];
            else if(px==3)
                tmp = (r[i][0] == 1) ? py + r[i][1] : w - py + r[i][1];
            else
                tmp = (r[i][0] == 1) ? py + h - r[i][1] : w - py + h - r[i][1];
        }
        ans += tmp;
    }
    cout << ans;
}

경비원 - 알고리즘닷컴
여기서는 https://acmicpc.net 의 문제를 기반으로 한 설명과 소스코드를 포스팅합니다.

36 개의 글