[C++] 백준 23247번: Ten

문제 링크

23247번: Ten

문제 요약

땅을 직사각형으로 묶어서, 그 합이 10이 되는 경우의 수를 출력해야 한다.

접근 방법

21년도 ICPC 인예 문제입니다. 제가 제일 쉬운 I번을 풀고 나서 바로 잡았던 문제였는데, 저는 풀이만 생각하고 구현은 다른 팀원이 했었습니다. 그래서 안 푼 상태로 방치했다가 그냥 오늘 풀어봤습니다.

사각형 내에 포함된 원소의 합이 10이 되어야 하는데, 만약 사각형의 크기가 10을 넘어간다면, 합이 10을 무조건 넘길 수밖에 없습니다. 그래서 미리 전처리로 2차원 누적합을 구해놓고, 왼쪽 위에서부터 순서대로, 크기가 10 이하인 사각형을 모두 검사해주는 식으로 풀이를 작성했습니다.

for문을 4개 중첩시켰다보니 코드가 깔끔하지는 않습니다.

코드

#include <bits/stdc++.h>

using namespace std;

const int MAX = 301;
int m, n, sum[MAX][MAX];

int prefix_sum(int y1, int x1, int y2, int x2) {
	return sum[y2][x2] - sum[y2][x1 - 1] - sum[y1 - 1][x2] + sum[y1 - 1][x1 - 1];
}

int main(void) {
	cin >> m >> n;

	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			int num;
			cin >> num;
			sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + num;
		}
	}

	int ans = 0;
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++)
			for (int k = 0; k <= 9; k++)
				for (int l = 0; l <= 9; l++)
					if ((k + 1) * (l + 1) <= 10 && (i + k) <= m && (j + l) <= n && prefix_sum(i, j, i + k, j + l) == 10)
						ans++;

	cout << ans << '\n';
	return 0;
}