취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 25275번 문제인 Bar Classification이다.
문제는 아래 링크를 확인하자.

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

어떤 한 행이 1로 이루어진 행이었다면 (그 행의 0 개수) + (배열의 다른 곳에 있는 1 개수)의 칸을 다시 flip하여 원상복구할 수 있어야 한다. 위의 값이 N 이하이면 그 행이 원래 처음 주어진 이미지였을 가능성이 존재한다. "배열의 다른 곳에 있는 1 개수"는 전체 1 개수를 미리 세둔다면 "그 행의 1개수"를 이용해 낮은 시간복잡도로 편하게 계산할 수 있다.

열 또한 위와 같은 논리로 접근해 문제를 해결하자.

아래는 제출한 소스코드이다.

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

int N;
string board[1000];
int cnt, rcnt[1000], ccnt[1000];

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

	cin >> N;
	for (int r = 0; r < N; r++) cin >> board[r];

	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			if (board[r][c] == '1') rcnt[r]++, ccnt[c]++, cnt++;
		}
	}


	bool chk1 = 0, chk2 = 0;
	for (int r = 0; r < N; r++) {
		if ((N - rcnt[r]) + (cnt - rcnt[r]) <= N) chk1 = 1;
	}
	for (int c = 0; c < N; c++) {
		if ((N - ccnt[c]) + (cnt - ccnt[c]) <= N) chk2 = 1;
	}

	if (chk1 && chk2) cout << '+';
	else if (chk1) cout << '-';
	else cout << '|';
}