[백준 2564] 경비원

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

2564번: 경비원

#include <stdio.h>
#include <stdlib.h>

int R, C;
int S;
int store[100 + 2][2 + 2];
int len_ans[100 + 2];

void input(void)
{
	scanf("%d %d", &R, &C);
	scanf("%d", &S);
	for (int i = 0; i < S + 1; i++) {
		scanf("%d %d", &store[i][0], &store[i][1]);	//S번째는 동근이의 위치
	}
}

void get_len(void)
{
	for (int i = 0; i < S + 1; i++) {
		if (store[i][0] == 1) len_ans[i] = store[i][1];	//북
		else if (store[i][0] == 2) len_ans[i] = R + C + (R - store[i][1]);	//남
		else if (store[i][0] == 3) len_ans[i] = (2 * R + C) + (C - store[i][1]);	//서
		else len_ans[i] = R + store[i][1];	//동
	}
}

int get_min(void)
{
	int total = 0;
	int dong = len_ans[S];
	for (int i = 0; i < S; i++) {
		int tmp = abs(dong - len_ans[i]);
		if (tmp > (R + C)) total += ((2 * (R + C)) - tmp);
		else total += tmp;
	}
	return total;

}


int main(void)
{
	input();
	get_len();
	printf("%d", get_min());
	return 0;
}

 

이문제 초등부 올림피아드 문제던ㄷㅔ.... ㅋ..상대적박탈감 오진다... ㅋㅋㅋㅋ

사실 아이디어도 생각하기 어려웠다. 근데 이 풀이 방법만 떠올리면 진짜 쉽게 풀린다.

 

//get_len 함수

이 문제의 키는 "직사각형 모양의 블록"을 "수직선"으로 생각하는 것이다. 즉 2차원을 1차원으로 생각하는 것이다. 

직사각형 모양 블록의 왼쪽 상단을 (0) 이라고 두면, 북쪽에 있는 1번 상점의 좌표는 (4) / 남쪽에 있는 3번 상점의 좌표는 (10 + 5 + 2 == 17) / 서쪽에 있는 2번 상점의 좌표는 (10 + 5 + 10 + 3 == 28) 이다. 마지막으로 동근이의 좌표는 (10 + 5 + 7 == 22) 이다. 

이렇게 두면 각 좌표 사이의 거리를 구하기가 매우 쉬워진다. 

 

//get_min 함수

또한 최단 거리를 구해야하기 때문에, 동근이와 상점 사이의 거리가  직사각형 블록 둘레의 절반(10 + 5)보다 크면 해당 방향이 아닌 다른 방향으로 도는 것이 더 효율적이다. 따라서 (전체 직사각형 블록 둘레) -  (동근이와 상점 사이의 거리) 를 해주면 최단거리가 나온다. 

 

댁아리를 더 많이 굴려야겠다.. 반성한 문제...