백준 BOJ 2564 - 경비원

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

2564번: 경비원

직사각형의 패러다임에서 생각하면 어려워지는 문제.

직사각형을 쭈우욱 펼쳐서 하나의 원형 지도를 상상한다.

거리 계산의 편의상 서북쪽 꼭짓점,

그러니까 왼쪽 위에 해당하는 부분을 0으로 시작해서

시계방향으로 원을 한바퀴 돌면 서북에 있는 꼭짓점과 각 점들간의 거리를 구할 수 있다.

이 거리를 $dis_i$ 라고 하고, 동근이의 점에 대해서도 거리를 구해서 $dis_d$ 라고 하자.

 

문제의 정의에 따라서,

경계로부터의 거리가 $K$ 일때 $dis_i$는

북쪽 : $K$

동쪽 : $R + K$

남쪽 : $2R + C - K$

서쪽 : $2R + 2C - K$

로 계산해 줄 수 있다.

 

다시 원을 하나의 수직선으로 펼쳐 생각해보면

수직선상의 두 점 $A$, $B$ 사이의 거리가 $ABS(A-B)$ 임에 따라

 

동근이가 각 상점을 시계방향으로 돌아서 이동할때의 거리는

$ABS( dis_i - dis_d )$ 가 된다.

반시계 방향으로 이동할 때는 원이라는 특성상

원의 원주에서 시계방향으로 이동한 거리만큼을 빼준

$2R + 2C - ABS(  dis_i - dis_d )$ 가 거리가 되며,

이 두 가지 경우 중 보다 작은 경우를 더해가며 계산하면 답을 구할 수 있다.

 

#include <bits/stdc++.h>
using namespace std;

int dis[123] = {0};
int pdis = 0;

int main(){
	int R,C,N;
	int a,b;
	
	cin >> R >> C;
	cin >> N;
	
	for(int i=0; i<=N; i++){
		cin >> a >> b;
		if(a == 1) dis[i] = b;
		if(a == 2) dis[i] = 2*R+C-b;
		if(a == 3) dis[i] = 2*(R+C)-b;
		if(a == 4) dis[i] = R+b;
	}
	
	int ans = 0;
	int tmp = 0;
	
	for(int i=0; i<N; i++){
		tmp = abs(dis[i] - dis[N]);
		ans += min(2*(R+C) - tmp, tmp);
	}
	cout << ans;
	return 0;
}

처음에 서북 꼭짓점에서 각 상점까지의 거리를 시계/반시계를 포함하는 최단경로로 정하면

경우에 따라서는 $ABS( dis_i + dis_n )$ 를 계산해야 할때도 있으므로

편의상 시계 / 반시계 한방향으로 통일하고 시작하는것이 좋을 것 같다.

이것때문에 한번 틀렸다 ㅠㅠ