취미로 코딩하기

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

이번에 볼 문제는 백준 12065번 문제인 gMatrix (Large)이다.
문제는 아래 링크를 확인하자.

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

모든 "K행K열의 부분행렬에 적힌 수의 최댓값"의 합을 구하는 문제이다.

각 행의 모든 연속한 길이 K의 구간의 최댓값은 deque을 이용한 trick으로 선형 시간 복잡도에 전부 구할 수 있다. 이 값들을 다시 열 방향으로 살피면 연속한 길이 K의 구간에 대한 최댓값, 즉 K행K열의 부분행렬에 대한 최댓값을 빠르게 전부 구할 수 있다.

위 관찰을 이용해 문제를 해결하자.

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

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

int N, K, CC, X;
int R[3001], C[3001];
int A[3001][3001];
deque<pair<int, int>> dq[3001]; // {최댓값, 열}

void solve() {
	ll ans = 0;
	cin >> N >> K >> CC >> X;
	for (int i = 1; i <= N; i++) cin >> R[i];
	for (int i = 1; i <= N; i++) cin >> C[i];
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			A[r][c] = ((ll)R[r] * r + (ll)C[c] * c + CC) % X;
		}
	}
	for (int r = 1; r <= N; r++) {
		auto &dque = dq[r];
		dque.clear();
		for (int c = 1; c < K; c++) {
			int val = A[r][c];
			while (!dque.empty() && dque.back().first <= val) dque.pop_back();
			dque.push_back(make_pair(val, c));
		}
	}
	for (int c = K; c <= N; c++) {
		deque<pair<int, int>> dqdq;
		for (int r = 1; r < K; r++) {
			auto &dque = dq[r];
			int val = A[r][c];
			while (!dque.empty() && dque.back().first <= val) dque.pop_back();
			dque.push_back(make_pair(val, c));
			while (dque.front().second + K <= c) dque.pop_front();
			val = dque.front().first;
			while (!dqdq.empty() && dqdq.back().first <= val) dqdq.pop_back();
			dqdq.push_back(make_pair(val, r));
		}
		for (int r = K; r <= N; r++) {
			auto &dque = dq[r];
			int val = A[r][c];
			while (!dque.empty() && dque.back().first <= val) dque.pop_back();
			dque.push_back(make_pair(val, c));
			while (dque.front().second + K <= c) dque.pop_front();
			val = dque.front().first;
			while (!dqdq.empty() && dqdq.back().first <= val) dqdq.pop_back();
			dqdq.push_back(make_pair(val, r));
			while (dqdq.front().second + K <= r) dqdq.pop_front();
			ans += dqdq.front().first;
		}
	}
	cout << ans << '\n';
}

int T;

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

	cin >> T;
	for (int t = 1; t <= T; t++) {
		cout << "Case #" << t << ": ";
		solve();
	}
}