[백준 2564] - 경비원(구현) C++

문제

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

2564번: 경비원

접근방법

처음엔 bfs문제로 풀 수 있을 거 같았다.

근데 입력값을 보고 테이블을 보니 bfs로 구현하기가 애매해보였다.

 

처음 시작점을 기준으로 떨어진 거리를 숫자로 표현할 수 있었다.

숫자를 계산하고, 동근이와 거리를 계산해주면 된다.

 

각 상점과 동근이 사이 최소 거리는 다음과 같이 계산한다.

1.동근이와의 거리를 계산한다. 

2.총 거리에서 동근와의 거리를 뺀 거리를 계산한다.

3.둘 중 작은 것을 선택한다.

 

min(abs(dongen - value), abs(2 * n + 2 * m - abs(value - dongen)))

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <deque>

using namespace std;

#define FOR(i, n) for(int i=0;i<n;i++) 
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define MAX 987654321
#define MIN -987654321

int m, n;
int num_store;
int arr[4];
vector<int> store;
int main() {
    int ret = 0;
    cin >> m >> n;
    cin >> num_store;
    int k = 0;
    FOR(i,3) {
        if (i % 2 == 0) k += n;
        else k += m;
        arr[i] = k;
    }
    int dir, dist;
    FOR(i, num_store+1) {
        cin >> dir >> dist;
        if (dir == 1) {
            store.push_back(arr[2] + (m-dist));
        }else if (dir == 2) {
            store.push_back(arr[0] + dist);
        }
        else if (dir == 3) {
            store.push_back(dist);
        }
        else if (dir == 4) {
            store.push_back(arr[1] + (n - dist));
        }
    }
    int dongen = store.back();
    store.pop_back();
    for (auto value : store) {
        ret += min(abs(dongen - value), abs(2 * n + 2 * m - abs(value - dongen)));
    }

    cout << ret << endl;



    return 0;
}

개선할 점

이거 푸는 데 이렇게 오래 걸리면 어떡하냐ㅜㅜ

 

구현 너무 어려우이..