BOJ 17037 - Painting the barn (발상, 누적합)

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

 

<문제설명>

1000이하의 자연수로 표현되는 좌표평면에 최대 1e5개의 직사각형모양 페인트를 칠할것.

 

k와 좌하단(x1,y1), 우상단(x2,y2)꼭지점으로 표현되는 직사각형들이 주어질 때, 페인트가 정확히 k겹 칠해진 부분의 넓이를 구해라.

 

<풀이>

int a[1001][1001] -> a[i][j]: 칸(i,j)에 페인트가 칠해진 횟수

 

직사각형이 최대 1e5개이므로, 직사각형 정보가 들어올 때마다 a[i][j]를 초기화하면 최악의 경우 1e5*1e3*1e3이므로 시간초과가 난다.

 

가로줄,세로줄을 따로 초기화한다는 아이디어가 필요하다.

 

처음엔 위쪽 경계선은 -1로, 아래쪽은 +1로 초기화 해둔다. 그 후 전체를 초기화한다.

 

말로하기가 어렵지만 코드를 눈으로 읽기만해도 다시 떠오를 것

 

<코드>

int n, k;
int a[1001][1001];

int main() {
	FAST;
	cin >> n >> k;
	for (int i = 0,x1,y1,x2,y2; i < n; i++) {
		cin >> x1 >> y1 >> x2 >> y2;
		for (int j = x1; j < x2; j++) {
			a[j][y1]++;
			a[j][y2]--;
		}
	}

	for (int i = 0; i < 1000; i++) 
		for (int j = 0; j < 1000; j++) 
			a[i][j + 1] += a[i][j];
	
	int cnt = 0;
	for (int i = 0; i < 1000; i++)
		for (int j = 0; j < 1000; j++) 
			if (a[i][j] == k) cnt++;
	
	cout << cnt << '\n';
}

 

<최적화한 코드>

int n, k;
int a[1001][1001];

int main() {
	FAST;
	cin >> n >> k;
	for (int i = 0,x1,y1,x2,y2; i < n; i++) {
		cin >> x1 >> y1 >> x2 >> y2;
		for (int j = x1; j < x2; j++) {
			a[j][y1]++;
			a[j][y2]--;
		}
	}
	int cnt = 0;
	for (int i = 0; i < 1000; i++) for (int j = 0; j < 1000; j++) {
		if (a[i][j] == k) cnt++;
		a[i][j+1] += a[i][j];
	}
	cout << cnt << '\n';
}

 

<구간합을 이용한 코드>

int dp[1001][1001];

int main() {
  int n, k;
  cin >> n >> k;
  while(n--) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    dp[a][b]++;	//좌하단
    dp[a][d]--;
    dp[c][b]--;
    dp[c][d]++; //우상단
  }
  int ret = 0;
  for(int i = 0; i < 1000; i++) {
    for(int j = 0; j < 1000; j++) {
      if(i) dp[i][j] += dp[i-1][j];
      if(j) dp[i][j] += dp[i][j-1];
      if(i && j) dp[i][j] -= dp[i-1][j-1];
      if(dp[i][j] == k) ret++;
    }
  }
  cout << ret << endl;
}

 

<생각>

구간합 이용한 부분도 유념해두자