[C++] 백준 1960번: 행렬만들기(시간 0ms 풀이)

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

1960번: 행렬만들기

 

 > 접근

그리디하게 풀릴 수 있을 것이라고 직감하여 고안해낸 방법은 다음과 같은 순서를 따른다.

 

즉, 1. row 단위로 크게 돌면서, 2. 현재 채워넣어야할 1의 개수가 가장 많은 곳을 채워넣는 것이다.

 

 > 풀이

이것을 위해 우선순위큐를 이용한다. 우선순위큐(columnInfo)에는 (채워넣어야할 1의 개수, 해당 column의 인덱스)를 넣어준다.

이후에 row 단위로 for문을 진행하는데, 이 때 해당 row에서 선택해야할 개수만큼 columnInfo에서 꺼내주고 matrix를 완성시켜나가게 된다.

이 때 first값을 -1 줄인 채로 우선순위큐에 다시 넣어주어야 하는데, 주의해야할 점은 poppedQueue에 이번 row에서 추가된 곳의 정보를 따로 빼준 뒤 그 다음에 우선순위큐에 넣어주어야한다는 것이다. 그 이유는 아래 tc에서 바로 알 수 있다.

7
2 4 3 4 5 2 5
4 5 0 7 2 4 3

1
0101000
1101010
0001011
1101001
1101110
0001001
1101110

4 5 0 7 2 4 3에서 7에 대한 원소를 선택하게 되는데, 이 때 columnInfo에서 빼주지 않으면, 또다시 같은 곳을 선택하게 되기 때문이다.

 

코드는 다음과 같다.

#include <iostream>
#include <queue>
using namespace std;

int n;
int rows[500];
int columns[500];
int matrix[500][500];

bool isMatrixValid() {
	int i, j;
	for (j = 0; j < n; j++) {
		int columnSum = 0;
		for (i = 0; i < n; i++) columnSum += matrix[i][j];

		if (columnSum != columns[j]) return false;
	}
	return true;
}

void solution() {
	int i, j;

	// 우선순위큐 초기화
	priority_queue<pair<int, int>> columnInfo; // (count, index) of column
	for (i = 0; i < n; i++) columnInfo.push({ columns[i], i });

	// row 단위로 greedy하게 진행
	for (i = 0; i < n; i++) {
		queue<pair<int, int>> poppedQueue; // 선택된 columnInfo의 원소들을 저장

		// 우선순위큐를 활용하여, 선택되어야할 column이 많은 것부터 선택
		for (j = 0; j < rows[i]; j++) {
			pair<int, int> popped = columnInfo.top(); columnInfo.pop();
			matrix[i][popped.second] = 1;
			poppedQueue.push({ popped.first - 1, popped.second });
		}

		// columnInfo <- poppedQueue
		while (!poppedQueue.empty()) {
			columnInfo.push(poppedQueue.front());
			poppedQueue.pop();
		}
	}

	// 행렬 체크
	if (!isMatrixValid()) {
		cout << "-1\n";
	}
	else {
		// 출력
		cout << "1\n";
		for (i = 0; i < n; i++) {
			for (j = 0; j < n; j++) cout << matrix[i][j];
			cout << "\n";
		}
	}
}

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

	cin >> n;

	int i;
	for (i = 0; i < n; i++) cin >> rows[i];
	for (i = 0; i < n; i++) cin >> columns[i];

	solution();

	return 0;
}