[BOJ] 18248 - 제야의 종

1. 문제 해석

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

18248번: 제야의 종

• 제야의 종소리는 특정 거리 R 이내에 있는 사람만 들을 수 있다.
• 거리 R의 값은 종을 칠 때마다 바뀐다.
• N명의 사람이 있고 M번 종을 친다. 사람들은 움직이지 않는다.
• N명에 사람 각가에 대한 각 M번의 타종을 들었는 지의 여부가 주어졌을 때, , 실제로 가능한 상확인 지

 

2. 접근방법

• N명의 위치 변화가 업기 때문에 M번의 타종에 대하여 가장 많은 타종을 들을 사람이 종과 가장 가까운 거리에 있다고 볼 수 있다.
• 만약에 A의 위치가 5이고 B의 위치가 7이라 하고 4번의 타종이 있다고 하자. 타종의 유료 거리 R1, R2, R3, R4는 각각 4, 6, 8, 9이다. R3, R4는 A와 B가 모두 들을 수 있지만 R2는 A만 들을 수 있다. R1은 둘 다 들을 수 없다.
• A가 듣지 못했다면 더 멀리 있는 B도 당연히 듣지 못한다. 따라서 A가 듣지 못했는데 B가 들었다면 불가능한 상황이다.

 

3. 주의할 점

• 각각의 사람이 들은 종소리의 개수와 거리의 관계를 생각해야한다. 

 

4. 소스코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N, M;
int board[1001][101];
vector<pair<int, int>> vec;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		int cnt = 0;
		for (int j = 0; j < M; j++) {
			cin >> board[i][j];
			if (board[i][j] == 1) cnt++;
		}
		vec.push_back({ cnt, i });
	}
	sort(vec.begin(), vec.end());
	bool isOk = true;
	for (int i = N - 1; i >= 0; i--) {
		int idx = vec[i].second;
		for (int j = 0; j < M; j++) {
			if (board[idx][j] == 0) {
				for (int k = i - 1; k >= 0; k--) {
					int cur = vec[k].second;
					if (board[cur][j] != 0) {
						isOk = false;
						break;
					}
				}
			}
			if (!isOk) break;
		}
		if (!isOk) break;
	}
	if (isOk) cout << "YES\n";
	else cout << "NO\n";

	return 0;
}