Boj 20543) 폭탄 던지는 태영이

문제

백준 20543

설명

무식하게 다 하면 시간복잡도가 O(n^4) 가 나옴.

여기서 해결 방법은 input 값이 약간의 조건이 더해진 누적 합이라는 것임.

시작점

• input 의 꼭짓점의 값은 가장 끝의 폭팔에만 영향을 받음.
• 여기가 시작점임
• 기준은 어떻게 잡아도 상관은 없는데 left top 을 시작점으로 잡아서 왼->오른으로 먼저 가고 위->아래 로 내려오면서 계산하겠음.

점화식

• 폭팔 함수를 B(x, y) 라고 하고, 폭탄 갯수 함수를 A(x, y) 라고 하겠음.
• input 이 범위가 m 이라는 제한이 없는 누적합이라고 생각해보겠음.
  • A(x, y) = -( B(x, y) - B(x-1, y) - B(x, y-1) + B(x-1, y-1) ) 가 성립함.
  • 이유는 누적합이기 때문에 간단히 생각가능함.
• 문제는 m 으로 제한이 있는 누적합이라는 것임
  • A(x, y) 를 기준으로
  • B(x-1, y) 는 A(x-1-m/2, y) 라는 값이 더해져 있는데, A(x, y) 에는 이 값이 없는 상태임.
  • B(x, y-1) 는 A(x, y-1-m/2) 라는 값이 더해져 있는데, A(x, y) 에는 이 값이 없는 상태임.
  • B(x-1, y-1) 는 A(x-1-m/2, y-1-m/2) 라는 값이 더해져 있는데, A(x, y) 에는 이 값이 없는 상태임.
  • 위 상태만 보정을 해주면 위에서 구한 누적합이란 가정이 성립하게 됨.
• 윗부분이 없거나 왼쪽 부분이 없는경우는 예외처리를 해주면 끝

시간 복잡도

O(n^2)

코드

using INT = int64_t;
int n, m;
INT board[2001 * 2001];
INT ans[2001 * 2001];

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

	for (int y = 0; y < n; y++)
		for (int x = 0; x < n; x++)
			cin >> board[n * y + x];
	
	if (m != 1)
	{
		m /= 2;
	
		int tmp;
		ans[n * m + m] = -board[0];
		for (int x = m + 1; x < n - m; x++) {
			ans[n * m + x] = board[x - m - 1] - board[x - m];
			if (x - m - m - 1 > 0)
				ans[n * m + x] += ans[n * m + x - m - m - 1];
		}
	
		for (int y = m + 1; y < n - m; y++)
		{
			ans[n * y + m] = board[n * (y - m - 1) + m - m] - board[n * (y - m) + m - m];
			if (y - m - m - 1 > 0)
				ans[n * y + m] += ans[n * (y - m - m - 1) + m];
			for (int x = m + 1; x < n - m; x++)
			{
				ans[n * y + x] =
					-board[n * (y - m - 1) + x - m - 1]
					+ board[n * (y - m - 1) + x - m]
					+ board[n * (y - m) + x - m - 1]
					- board[n * (y - m) + x - m];
				if (x - m - m - 1 > 0)
					ans[n * y + x] += ans[n * y + x - m - m - 1];
				if (y - m - m - 1 > 0)
					ans[n * y + x] += ans[n * (y - m - m - 1) + x];
				if (x - m - m - 1 > 0 && y - m - m - 1 > 0)
					ans[n * y + x] -= ans[n * (y - m - m - 1) + x - m - m - 1];
			}
		}
	
		for (int y = 0; y < n; y++)
		{
			for (int x = 0; x < n; x++)
				cout << ans[n * y + x] << ' ';
			cout << '\n';
		}
	}
	else {
		for (int y = 0; y < n; y++)
		{
			for (int x = 0; x < n; x++)
				cout << -board[n * y + x] << ' ';
			cout << '\n';
		}
	}
}