0으로 초기화되있는 2차원 배열이 주어진다.
행또는 열에 들어있는 모든 숫자들을 1씩 증가시킬 수 있다.
이러한 연산을 했을 때 다음의 배열을 만들 수 있는가와 만드는 방법을 구하는 문제이다.
3월에 풀어봤다가 계속 틀리길래 AC코드를 저장해놓고 참고해서 다시 풀어봤다.
우선 완성된 배열을 모두 0으로 만들 수 있는지에 대한 풀이로 푼다.
불가능한 경우는 각 행을 최소화 시켰을 경우 남아있는 열들의 값이 불일치하는 경우이다.
(반대로 각 열을 최소화시켰을 때 남아있는 행의 값이 불일치해도 동일)
1 1 1 1 → 0 0 0 0
2 2 1 1 → 1 1 0 0
1 1 1 1 → 0 0 0 0
1 1 2 2 → 0 0 1 1
값을 구하려면 행이 열보다 더 큰경우와 아닌경우로 나누어 greedy하게 구하면 된다.
#include <cstdio>
#include <algorithm>
using namespace std;
#define INF 987654321
int N, M;
int minRow[501], minCol[501];
int mat[501][501];
bool isPossible() {
for (int m = 0;m < M;m++) {
int get = mat[0][m] - minRow[0];
for (int n = 0;n < N;n++) {
if (get != mat[n][m] - minRow[n]) return false;
}
minCol[m] = get;
}
return true;
}
void solve() {
int cnt = 0;
for (int n = 0;n < N;n++) {
cnt += minRow[n];
}
for (int m = 0;m < M;m++)
cnt += minCol[m];
printf("%d\n", cnt);
for (int n = 0;n < N;n++) {
for (int t = 0;t < minRow[n];t++)
printf("row %d\n", n + 1);
}
for (int m = 0;m < M;m++) {
for (int t = 0;t < minCol[m];t++)
printf("col %d\n", m + 1);
}
}
int main() {
scanf("%d%d", &N, &M);
for (int n = 0;n < N;n++) {
minRow[n] = INF;
for (int m = 0;m < M;m++) {
scanf("%d", &mat[n][m]);
minRow[n] = min(minRow[n], mat[n][m]);
}
}
if (!isPossible()) printf("-1\n");
else {
if (N <= M) {
solve();
}
else {
for (int m = 0;m < M;m++) {
minCol[m] = INF;
for (int n = 0;n < N;n++) {
minCol[m] = min(minCol[m], mat[n][m]);
}
}
for (int n = 0;n < N;n++) {
minRow[n] = mat[n][0] - minCol[0];
}
solve();
}
}
return 0;
}
| cs |
댓글 없음:
댓글 쓰기