[백준] 23247 Ten (C++)

23247번: Ten

지난 토요일에 참가한 ICPC Seoul Regional 2021 예선 J번 문제이다. 대회 중에 맞췄었던 문제이다. 대회 때 내가 풀어서 기분 좋아서 풀이를 올려본다!

 

문제를 간단히 요약하면...

위 사진과 같이 행렬에 수들이 주어졌을 때, (가로와 세로가 행과 열에 평행한) 직사각형 안의 수들의 합이 10이 되는 직사각형의 개수를 구하는 것이다. 즉, 위 그림의 답은 4이다.

---

풀이

아래의 풀이에서 (x,y) 순서쌍은 x행 y열을 의미합니다.

 

문제의 풀이를 간단하게 요약하면 다음과 같다.

1. 입력을 받고 (1,1)부터 각 자리까지의 누적합을 계산하여 sum배열에 저장.

2. 모든 점에 대해(브루트포스!!) 해당 점이 직사각형의 왼쪽 위 꼭짓점이고 합이 10인 직사각형이 있는지 탐색.

 

 

우선 1행 1열부터 i행 j열까지의 누적합을 구하는 식은 다음과 같다.

sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + table[i][j];

 

 

이제 구해둔 누적합을 이용하여 (x, y)부터 (i, j)까지의 합(코드에서 tmp)을 나타내면 다음과 같다.

tmp = sum[i][j] - sum[i][y - 1] - sum[x - 1][j] + sum[x - 1][y - 1];

 

 

따라서, tmp값이 10이면  답인 ans값을 증가시켜준다. 이를 수행하는 함수는 다음과 같다.

void func(ll x, ll y) {
	for (ll i = x; i <= m; i++) {
		for (ll j = y; j <= n; j++) { //x행y열부터 i행 j열까지 합이 10인지 검사
			ll tmp = sum[i][j] - sum[i][y - 1] - sum[x - 1][j] + sum[x - 1][y - 1];
			if (tmp >= 10) {
				if (tmp == 10) ans++;
				break;
			}
		}
	}
}

tmp가 10이거나 10보다 크면 break를 해주었다. 그 이유는 이미 (x,y)부터 (i,j)까지의 합이 10 이상인데, j를 증가시키면 합이 10보다 더 커지기 때문이다.

 

아래의 '더보기'에 자세히 설명하였다.

(x, y)가 (1,1)이고, (i, j)가 (2, 3)인 상황을 아래 그림을 통해 살펴보자.

파랑색 영역의 총합이 (1, 1)부터 (2, 3)까지의 총합이다.

즉, 파란색 영역의 총합을 계산한다. 이 값이 10보다 크다면 j값이 1이 커져서 (i, j)가 (2,4)가 되면 그 전 상황(이미 10보다 크다)보다 영역의 합이 더 커지기 때문에 빨간색 영역의 합은 확인할 필요가 없다.

그러므로 다음으로 확인할 영역은 (1, 1)부터 (3, 1)까지의 총합인 노란색 영역이 되는 것이다.

(이 노란색 영역의 합이 10보다 작다면 다음으로 확인할 영역은 (1, 1)부터 (3, 2)까지가 될 것이다.)

 

---

코드

#include <bits/stdc++.h>
#define endl '\n'
#define INF 9876543210
using namespace std;
using ll = long long;

ll m, n, ans = 0;
ll table[301][301];
ll sum[301][301]; //sum[i][j]는 1,1부터 i,j까지의 총 합

void func(ll x, ll y) {
	for (ll i = x; i <= m; i++) {
		for (ll j = y; j <= n; j++) { //x행y열부터 i행 j열까지 합이 10인지 검사
			ll tmp = sum[i][j] - sum[i][y - 1] - sum[x - 1][j] + sum[x - 1][y - 1];
			if (tmp >= 10) {
				if (tmp == 10) ans++;
				break;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	cin >> m >> n;
	for (ll i = 1; i <= m; i++) {
		for (ll j = 1; j <= n; j++) {
			cin >> table[i][j];
		}
	}
	for (ll i = 1; i <= m; i++) {
		for (ll j = 1; j <= n; j++) {
			sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + table[i][j];
		}
	}
	for (ll i = 1; i <= m; i++) {
		for (ll j = 1; j <= n; j++) {
			func(i, j);
		}
	}
	cout << ans << endl;

	return 0;
}