백준 27499 - 레이저 쏘기

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

27499번: 레이저 쏘기

발상의 전환이 필요한 문제. 이걸 떠올리고 나면 생각보다 금방 풀린다. 일단 핵심부터 말하자면, 레이저를 센서를 향해 무작정 직접 쏘는 것 만이 정답은 아니다. (무작정이 포인트임)

이런 경우의 수도 존재한다.

 

위 그림을 이렇게 나타내면 어떨까?

센서를 벽에 한번 반사시켰더니, 레이저를 센서를 향해 직접 쏘는 꼴이 되었다.

 

이제 문제를 보는 시야가 바뀐다.

최대 반사 가능 횟수 K에 대해, 존재하는 N개의 센서를 벽에 K-1번 반사시킨다. 총 N*(K-1) 개의 센서가 생길 것이다.

 N*(K-1) 개의 센서에 대해 원점과 센서를 잇는 직선의 기울기를 계산한다. 기울기가 같다면 K번 미만의 반사를 통해 동시에 연결할 수 있는 센서일 것이다. 나는 기울기를 map<double>을 이용해 구현했지만, double의 정밀도는 불안정한 요소가 있으므로 가능하면 정수끼리의 나눗셈을 안전하게 비교하는 다른 방식을 찾아보는 것을 권장한다.

 

코드

vector<int> vec_x[1001];
vector<int> vec_y;
int n, width, k;

void solve();

int main() {

	cin >> n >> width >> k;

	//x좌표는 n * k개 존재한다
	int x, y;
	for (int i = 0; i < n; i++) {
		cin >> x >> y;
		vec_x[i].push_back(x);
		vec_y.push_back(y);
	}

	solve();
}

void solve() {
	//n개의 센서를 벽에 k-1번 반사시킨다
	int new_x;
	for (int i = 0; i < n; i++) {
		for (int j = 1; j < k; j++) {
			new_x = j * width;
			if (j % 2)
				new_x = new_x + width - vec_x[i][0];
			else
				new_x += vec_x[i][0];
			vec_x[i].push_back(new_x);
		}
	}

	//n * k개의 점에 대해 기울기를 구한다
	map<double, int> m;
	int max = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < k; j++) {
			double slope = (double)vec_y[i] / vec_x[i][j];
			m[slope]++;
			if (m[slope] > max)
				max = m[slope];
		}
	}

	cout << max << endl;
}

 

그림을 더 그리면 이해하기 편할텐데 시간이 없어서 여기까지만 쓴다.