취미로 코딩하기

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

이번에 볼 문제는 백준 24450번 문제인 国土分割 (Land Division)이다.
문제는 아래 링크를 확인하자.

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

가로선과 세로선을 동시에 그어 국토분할이 제대로 이루어진 경우를 생각해보면, 각 분할된 칸 안에 적힌 수의 합이 각각 같은 상황이라는 의미이므로 가로선만으로 분할된 국토 및 세로선만으로 분할된 국토들도 각 분할에 적힌 수의 합이 같게 된다. 즉, 가로선과 세로선을 동시에 그어 국토분할이 이루어지는 경우의 수는 가로선만으로 분할할 수 있는 방법들과 세로선만으로 분할할 수 있는 방법들의 조합만을 살펴 실제로 분할이 이루어지는지를 확인해보는 것으로 계산해낼 수 있게 된다.

따라서, 가로선만을 긋는 방법과 세로선만을 긋는 방법들을 먼저 찾아내고 두 방법의 조합별로 선을 그었을 때 분할이 제대로 이루어지는지를 체크하는 것으로 문제를 해결할 수 있다.

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

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

int R, C;
ll board[51][51];
ll rsum[51], csum[51], total = 0;
vector<vector<int>> rpartition, cpartition;

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

	cin >> R >> C;
	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) {
			ll& x = board[r][c];
			cin >> x;
			rsum[r] += x, csum[c] += x, total += x;
		}
	}

	for (int k = 1; k <= R; k++) { // row들을 k개로 partition
		if (total % k) continue;
		ll val = total / k;
		ll psum = 0;
		bool chk = 1;
		vector<int> partition;
		for (int r = 1; r <= R; r++) {
			psum += rsum[r];
			if (psum > val) {
				chk = 0;
				break;
			}
			else if (psum == val) {
				partition.emplace_back(r);
				psum = 0;
			}
		}

		if (chk) rpartition.emplace_back(partition);
	}
	for (int k = 1; k <= C; k++) { // col들을 k개로 partition
		if (total % k) continue;
		ll val = total / k;
		ll psum = 0;
		bool chk = 1;
		vector<int> partition;
		for (int c = 1; c <= C; c++) {
			psum += csum[c];
			if (psum > val) {
				chk = 0;
				break;
			}
			else if (psum == val) {
				partition.emplace_back(c);
				psum = 0;
			}
		}

		if (chk) cpartition.emplace_back(partition);
	}

	int ans = 0;
	for (auto& rp : rpartition) {
		for (auto& cp : cpartition) {
			int rsize = rp.size(), csize = cp.size();
			int k = rsize * csize;
			if (total % k) continue;

			ll val = total / k;
			bool chk = 1;
			int oldr = 1;
			for (auto& r : rp) {
				int oldc = 1;
				for (auto& c : cp) {
					ll tmp = 0;
					for (int rr = oldr; rr <= r; rr++) {
						for (int cc = oldc; cc <= c; cc++) {
							tmp += board[rr][cc];
						}
					}
					if (tmp != val) chk = 0;
					oldc = c + 1;
				}
				oldr = r + 1;
			}
			if (chk) ans++;
		}
	}

	cout << ans - 1;
}