[BOJ] 1566_p배열

p배열

문제 링크: https://www.acmicpc.net/problem/1566

1566번: P배열

 

2차 시도 (실패)

case를 크게 2가지로 나누어서 해결한다.

1. 행 우선 검사
2. 열 우선 검사

각 행 또는 열의 합을 해당 줄 끝 19번째 자리에 저장한다.
ex) matrix[3][19]: 3번째 행의 합이 저장되어 있음
그리고 각 행 또는 열을 검사를 시작한다.
합만 비교하며 0보다 작은 경우 flip을 한다. 그리고 count한다.

모든 합이 0 이상인 경우 더 이상 flip할 필요가 없으므로 끝낸다.

출력은 행 우선 검사 와 열 우선 검사 중 더 작은 count를 출력한다.
그리고 모두 합이 양수인데, 합이 0인 경우가 있을 경우는 더 이상 flip을 통해 p배열을 만들 수 없다.
이 경우에 -1을 출력한다.

 

• 미해결 코드

   

•  

  #include<iostream>
  using namespace std;
  
  int matrix[20][20];
  int cpy_matrix[20][20];
  int n, m;
  
  void copyTotemp() {
  	for (int y = 1; y <= n; y++) 
  		for (int x = 1; x <= m; x++)
  			cpy_matrix[y][x] = matrix[y][x];
  }
  void copyToOrigin() {
  	for (int y = 0; y <= n; y++)
  		for (int x = 0; x <= m; x++)
  			matrix[y][x] = cpy_matrix[y][x];
  }
  void setup() {
  	for (int y = 0; y < 20; y++) {
  		matrix[y][0] = 0;
  		matrix[y][19] = 0;
  	}
  	for (int x = 0; x < 20; x++) {
  		matrix[0][x] = 0;
  		matrix[19][x] = 0;
  	}
  }
  
  void rowSum() {
  	int sum = 0;
  	// 행 합계산
  	for (int y = 1; y <= n; y++) {
  		for (int x = 1; x <= m; x++)
  			sum += matrix[y][x];
  		matrix[y][19] = sum;
  		sum = 0;
  	}	
  }
  void colSum() {
  	int sum = 0;
  	// 열 합계산
  	for (int x = 1; x <= m; x++) {
  		for (int y = 1; y <= n; y++)
  			sum += matrix[y][x];
  		matrix[19][x] = sum;
  		sum = 0;
  	}
  }
  
  void rowFlip(int idx) {
  	for (int x = 1; x <= m; x++) {
  		matrix[idx][x] *= -1;
  	}
  }
  void colFlip(int idx) {
  	for (int y = 1; y <= n; y++) {
  		matrix[y][idx] *= -1;
  	}
  }
  
  pair<bool, bool> AllCheck() {
  	pair<bool, bool> flag;
  	flag.first = false;
  	flag.second = false;
  	for (int y = 1; y <= n; y++) {
  		if (matrix[y][19] < 0) {
  			flag.first = true;
  		}
  		else if (matrix[y][19] == 0)
  			flag.second = true;
  	}
  
  	for (int x = 1; x <= m; x++) {
  		if (matrix[19][x] < 0) {
  			flag.first = true;
  		}
  		else if (matrix[19][x] == 0)
  			flag.second = true;
  	}
  	return flag;
  }
  
  void print() {
  
  	cout << endl;
  	for (int y = 0; y <= n; y++) {
  		for (int x = 0; x <= m; x++)
  			cout << matrix[y][x] << ' ';
  		cout << endl;
  	}
  	cout << endl;
  
  }
  
  int main() {
  	setup();
  	ios_base::sync_with_stdio(false);
  	cin.tie(NULL); cout.tie(NULL);
  
  	cin >> n >> m;
  
  	for (int y = 1; y <= n; y++)
  		for (int x = 1; x <= m; x++)
  			cin >> matrix[y][x];
  
  	pair<bool, bool> flag1;
  	flag1.first = true;
  
  	int count = 0;
  	print();
  	copyTotemp();
  
  	rowSum();
  	colSum();
  	while (flag1.first) {
  		//행 체크
  		for (int y = 1; y <= n; y++) {
  			if (matrix[y][19] < 0) {
  				//flip
  				rowFlip(y);
  				matrix[y][0]++; //해당 행 flip 1회
  				count++;
  			}
  		}
  		colSum(); //행에서 갱신되었을 수 있기에 열의 합 구함
  		//열 체크
  		for (int x = 1; x <= m; x++) {
  			if (matrix[19][x] < 0) {
  				//flip
  				colFlip(x);
  				matrix[0][x]++; //해당 열 flip 1회
  				count++;
  			}
  		}
  		rowSum(); //열에서 갱신되었을 수 있기에 행의 합 구함
  		flag1 = AllCheck();
  	}
  
  	print();
  
  	copyToOrigin();
  
  	print();
  
  	pair<bool, bool> flag2;
  	flag2.first = true;
  
  	rowSum();
  	colSum();
  
  	int count2 = 0;
  	while (flag2.first) {
  		//열 체크
  		for (int x = 1; x <= m; x++) {
  			if (matrix[19][x] < 0) {
  				//flip
  				colFlip(x);
  				matrix[0][x]++; //해당 열 flip 1회
  				count2++;
  			}
  		}
  
  		rowSum(); //열에서 갱신되었을 수 있기에 행의 합 구함
  		//행 체크
  		for (int y = 1; y <= n; y++) {
  			if (matrix[y][19] < 0) {
  				//flip
  				rowFlip(y);
  				matrix[y][0]++; //해당 행 flip 1회
  				count2++;
  			}
  		}
  		colSum(); //행에서 갱신되었을 수 있기에 열의 합 구함
  		flag2 = AllCheck();
  	}
  
  	print();
  
  	if (flag1.second && flag2.second)
  		cout << -1;
  	else
  		cout << ((count < count2) ? count : count2);
  
  	return 0;
  }