[백준] 경비원

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

2564번: 경비원

우선 문제부터 요약하면, 

 

직사각형 모양의 땅의 가장 바깥 경계에 동근이가 근무를 서고, 경계에 상점들 또한 존재합니다. 동근이와 상점들 사이의 최단거리의 합을구해야 하는 문제입니다. 

 

<Solution>

원탁모양이라고 생각해서, 좌상단을 0, 그리고 시계방향으로 0, 1, 2, 3 등으로 숫자가 매핑될 수 있도록 하였습니다.

 

그렇게 각각의 좌표들을 변환 시킨 후, 양 방향으로 이동하는 거리중 최솟값을 뽑아서 계속 더해주는 형태로 문제를 해결하면 됩니다.

 

실제 구현은 아래와 같습니다.

#include <iostream>
#include <cstdlib>

using namespace std;

int w, h, n;
int dir[100+10];
int len[100+10];

int changed_pos[100+10];

void InputData(){
    cin >> w >> h; // c, r
    cin >> n;
    for (int i=0; i<=n; i++){
        cin >> dir[i] >> len[i];
    }
}
// 0,0 부터 시계방향으로 0 , 1 , 2 ...로 변환

int solution(){
    int total = (w+h) * 2;

    // start index of n s w e

    int north = 0;
    int south = 2*w+h;
    int west = total;
    int east = w;

    for(int i = 0; i<=n; i++){
        if(dir[i] == 1){
            changed_pos[i] = len[i] + north;
        }
        else if(dir[i] == 2){
            changed_pos[i] = south - len[i];
        }
        else if(dir[i] == 3){
            changed_pos[i] = west - len[i];
        }
        else{
            changed_pos[i] = east + len[i];
        }

    }
    int ret = 0;

    for(int i = 0; i<n; i++){
        int tmp = abs(changed_pos[i] - changed_pos[n]);
        ret += min(tmp, total-tmp);

    }
    return ret;

}


int main(){
    int ans = -1;

    InputData();

    ans = solution();


    cout << ans << endl;
    return 0;
}