백준 2564번 경비원

문제 이해

블록의 가장자리로만 이동이 가능할 때, 동근이와 각 상점까지의 최소 거리의 합을 구하는 문제다.

 

위의 그림에서 동근이는 X, 상점은 1, 2, 3이다.

상점 1까지의 최소 거리는 12, 2까지는 6, 3까지는 5이고 그 합은 23이다. 

 

풀이 설명

동근이가 있는 면을 기준으로 왼쪽이나 오른쪽 면에 있는 상점들까지의 최소 거리는 각각 왼쪽으로 가는 길, 오른쪽으로 가는 길이다. 하지만 반대편에 있는 상점은 동근이를 기준으로 왼쪽으로 도는것과 오른쪽으로 도는 것 중 하나가 최소 거리다.

입력은 동서남북을 각각 4, 3, 2, 1로, 해당하는 면에서 상점의 위치는 가로면은 왼쪽부터, 세로면은 위쪽부터의 거리로 주어진다. 그렇기 때문에 동근이가 어떤 면에 있느냐에 따라 계산 식이 달라진다. 

 

하지만 위의 그림처럼 모든 점의 위치를 왼쪽 위 꼭짓점부터의 거리로 바꿔주면 계산하기 쉽다. 단순히 동근이의 위치에서 상점의 위치를 빼주면 둘 사이의 거리를 구할 수 있다. 그리고 상점이 동근이의 반대편에 있는 경우를 고려하여 블럭의 둘레 (2 * w + 2 * h)에서 이전에 구한 거리를 빼주고, 그 값과 이전에 구한 값 중 더 작은값으로 더해준다.

 

구현

// 2564 경비원

#include <cstdio> 
using namespace std;

int w, h, n, loc[101], sum;

int absf(int a) { return a < 0 ? -a : a; }
int minf(int a, int b) { return a < b ? a : b; }

int main() {
	scanf("%d%d%d", &w, &h, &n);
	
	for (int i = 0; i <= n; i++) {
		int cardinal, location;
		scanf("%d%d", &cardinal, &location);
		
		if (cardinal == 1) {
			loc[i] = location;
		}
		else if (cardinal == 2) {
			loc[i] = 2 * w + h - location;
		}
		else if (cardinal == 3) {
			loc[i] = 2 * w + 2 * h - location;
		}
		else if (cardinal == 4) {
			loc[i] = w + location;
		}
	}
	
	for (int i = 0; i < n; i++) {
		int dist = absf(loc[n] - loc[i]);
		sum += minf(dist, 2 * w + 2 * h - dist);
	}
	
	printf("%d", sum);
	
	return 0;
}

 

생각하지 못했던 부분

처음에는 동근이가 어떤 면에 있는지에 따라 왼쪽, 오른쪽 면이 무엇인지 배열로 기록해두고 계산했다.

 int relative[5][2] = { {0, 0}, 
                        {4, 3},
                        {3, 4},
                        {1, 2},
                        {2, 1} };

 

위의 풀이처럼 어떠한 점을 기준으로 상점과 동근이의 위치를 나타낸다는 아이디어는 있었지만, 거리를 어떻게 계산해야 할지 감을 못잡았다. 만약에 그림을 그려봤다면 눈에 잘 들어왔을 것 같다. (풀이참고)

 

문제 링크: www.acmicpc.net/problem/2564