dp1[x]를 1번 객차부터 x번 객차까지의 범위에서 K개의 연속한 객차를 하나의 소형기관차를 이용해 끌고갈 때 최대로 옮길 수 있는 손님의 수로 정의하자(단, x는 K보다 크다.). 소형기관차가 객차를 끄는 방법은 x번 객차를 끌거나 끌지 않는 두 가지로 구분할 수 있다. 각 경우의 옮길 수 있는 최대 손님의 수는 dp[x-1]과 dp[x-K], 그리고 x-K+1~x번 객차의 손님의 수의 합을 이용하면 계산해낼 수 있음을 관찰하자. 후자의 값은 prefix sum 배열을 미리 전처리해두는 것으로 빠르게 계산할 수 있다.
위와 같은 방식으로 dp2[x] 및 dp3[x] 또한 정의해 그 값들을 구해내자. 이 때 문제의 답은 dp3[N]이 될 것이다.
이 방법의 시간복잡도는 \(O(N)\)이다.
아래는 제출한 소스코드이다.
#include <iostream>
using namespace std;
int N, K;
int psum[50001];
int dp1[50001];
int dp2[50001];
int dp3[50001];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> psum[i];
psum[i] += psum[i - 1];
}
cin >> K;
for (int i = K; i <= N; i++) dp1[i] = max(dp1[i - 1], psum[i] - psum[i - K]);
for (int i = K * 2; i <= N; i++) dp2[i] = max(dp2[i - 1], dp1[i - K] + psum[i] - psum[i - K]);
for (int i = K * 3; i <= N; i++) dp3[i] = max(dp3[i - 1], dp2[i - K] + psum[i] - psum[i - K]);
cout << dp3[N];
}
먼저, 구현을 편하게 하기 위해 주어진 도형을 각 점과 선의 "두께"를 1로 늘려 새로 그리자. 시간 제한과 메모리 제한을 생각하지 않는다면, 새로 그린 도형의 (도형의 바깥을 제외한) 각 영역에 대하여 행 또는 열이 다른 직선의 연장선에 포함되지 않은 칸들의 개수의 최댓값을 구하는 것으로 문제를 해결할 수 있을 것이다.
시간 제한과 메모리 제한을 통과하기 위해 각 점들의 좌표를 1000 이하의 정수로 줄이고, 각 칸의 너비와 높이가 줄어들기 전에 얼마였는지를 기록하는 방식을 이용하자. 이 때 각 영역의 칸의 개수를 세는 과정은 각 칸의 너비와 높이를 곱한 값의 합을 구하는 것으로 바뀐다. 다른 직선의 연장선에 해당하는 칸의 경우 그 직선의 방향에 따른 높이 또는 너비를 0으로 계산하면 별다른 예외처리 없이 이를 구현해낼 수 있음을 확인하자.
위와 같이 구현할 경우 시간복잡도는 \(O(N^2)\)이 되고, 이는 문제를 해결하기에 충분한 시간복잡도이다.
아래는 제출한 소스코드이다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
int N;
int R[1000], C[1000];
int dR[1000], dC[1000];
int compr_R[10001], compr_C[10001];
pair<int, int> points[1000];
int board[1001][1001];
int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };
int dfs(int r, int c) {
board[r][c] = 1;
int ret = dR[r] * dC[c];
for (int i = 0; i < 4; i++) {
int rr = r + dr[i], cc = c + dc[i];
if (rr<0 || rr>N || cc<0 || cc>N || board[rr][cc]) continue;
ret += dfs(rr, cc);
}
return ret;
}
bool comp(pair<int, int>& p1, pair<int, int>& p2) {
if (p1.second != p2.second) return p1.second < p2.second;
return p1.first < p2.first;
}
int ans;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 0; i < N; i++) {
int& r = R[i], & c = C[i]; cin >> r >> c;
points[i] = make_pair(r, c);
}
sort(R, R + N);
for (int i = 0, idxR = 0; i < N; i++) {
if (!compr_R[R[i]]) {
if (i) dR[idxR * 2] = R[i] - R[i - 1];
compr_R[R[i]] = idxR++ * 2 + 1;
}
}
sort(C, C + N);
for (int i = 0, idxC = 0; i < N; i++) {
if (!compr_C[C[i]]) {
if (i) dC[idxC * 2] = C[i] - C[i - 1];
compr_C[C[i]] = idxC++ * 2 + 1;
}
}
for (int i = 0; i < N; i++) {
points[i].first = compr_R[points[i].first];
points[i].second = compr_C[points[i].second];
}
sort(points, points + N);
for (int i = 0; i < N; i += 2) {
int r = points[i].first, c1 = points[i].second, c2 = points[i + 1].second;
if (c1 > c2) swap(c1, c2);
for (int c = c1; c <= c2; c++) {
board[r][c] = 1;
}
}
sort(points, points + N, comp);
for (int i = 0; i < N; i += 2) {
int r1 = points[i].first, r2 = points[i + 1].first, c = points[i].second;
if (r1 > r2) swap(r1, r2);
for (int r = r1; r <= r2; r++) {
board[r][c] = 1;
}
}
dfs(0, 0);
for (int r = 0; r <= N; r++) {
for (int c = 0; c <= N; c++) {
if (!board[r][c]) ans = max(ans, dfs(r, c));
}
}
cout << ans;
}
주어진 잘린 영역이 단순 사각형이 아닐 필요충분조건 중 하나로 주어진 N개의 점 중 하나가 내각 270도의 꼭짓점으로 포함되어있어야 할 것이 있음을 관찰하자. 내각 270도의 꼭짓점이 존재하지 않는 다각형은 단순 사각형이 될 수밖에 없고, 그러한 각도를 가질 수 있는 꼭짓점은 문제 조건에 따라 주어진 N개의 점에서 나올 수밖에 없기 때문이다.
글쓴이는 구현을 편하게 하기 위해 먼저 주어진 그림을 각 점과 선의 "두께"를 1로 늘려 새로 그렸다. 그 다음, 이 새 그림에 존재하는 "단순 사각형이 아닌 영역"을 메워버린 다음(위의 필요충분조건 이용) (3) 남아있는 영역의 개수를 세는 것으로 문제를 해결하자. 단순 사각형이 아닌 영역을 모두 메우면 남는 영역은 각각 단순 사각형임을 확인하자.
시간제한에 맞춰 통과해야하므로, 먼저 주어진 좌표들을 압축하도록 하자.
한편, 주어지는 입력의 꼭짓점들이 다각형을 이루는 순서대로 주어진다는 보장이 지문에 없음에 유의하자. 따라서 주어진 꼭짓점들로부터 선분들을 찾는 것부터 시작하자. 다행히 문제의 조건을 만족하는 꼭짓점들이 주어지면 이러한 선분의 구성은 유일함을 알 수 있다.
이 모든 과정의 시간복잡도는 \(O(N^2)\)으로, 이는 문제를 해결하기에 충분한 값이다.
아래는 제출한 소스코드이다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
int N;
pair<int, int> points[1000];
vector<int> R, C;
int compr_R[10001], compr_C[10001];
char board[1001][1001];
bool comp(pair<int, int>& p1, pair<int, int>& p2) {
if (p1.second != p2.second) return p1.second < p2.second;
return p1.first < p2.first;
}
int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };
void dfs(int r, int c) {
board[r][c] = 2;
for (int i = 0; i < 4; i++) {
int rr = r + dr[i], cc = c + dc[i];
if (rr < 0 || rr > N || cc < 0 || cc > N || board[rr][cc]) continue;
dfs(rr, cc);
}
}
int cnt;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 0; i < N; i++) {
int r, c; cin >> r >> c;
points[i] = make_pair(r, c);
R.emplace_back(r), C.emplace_back(c);
}
sort(R.begin(), R.end());
for (int i = 0, ridx = 0; i < N; i++) {
if (!compr_R[R[i]]) compr_R[R[i]] = ridx++ * 2 + 1;
}
sort(C.begin(), C.end());
for (int i = 0, cidx = 0; i < N; i++) {
if (!compr_C[C[i]]) compr_C[C[i]] = cidx++ * 2 + 1;
}
for (int i = 0; i < N; i++) {
points[i].first = compr_R[points[i].first], points[i].second = compr_C[points[i].second];
}
sort(points, points + N);
for (int i = 0; i < N; i += 2) {
int r = points[i].first, c1 = points[i].second, c2 = points[i + 1].second;
if (c1 > c2) swap(c1, c2);
for (int c = c1; c <= c2; c++) {
board[r][c] = 1;
}
}
sort(points, points + N, comp);
for (int i = 0; i < N; i += 2) {
int r1 = points[i].first, r2 = points[i + 1].first, c = points[i].second;
if (r1 > r2) swap(r1, r2);
for (int r = r1; r <= r2; r++) {
board[r][c] = 1;
}
}
for (int i = 0; i < N; i++) {
int r = points[i].first, c = points[i].second;
if (board[r + 1][c] == 1 && board[r][c + 1] == 1) {
if (!board[r - 1][c - 1]) dfs(r - 1, c - 1);
}
else if (board[r + 1][c] == 1 && board[r][c - 1] == 1) {
if (!board[r - 1][c + 1]) dfs(r - 1, c + 1);
}
else if (board[r - 1][c] == 1 && board[r][c + 1] == 1) {
if (!board[r + 1][c - 1]) dfs(r + 1, c - 1);
}
else if (board[r - 1][c] == 1 && board[r][c - 1] == 1) {
if (!board[r + 1][c + 1]) dfs(r + 1, c + 1);
}
}
for (int r = 0; r <= N; r++) {
for (int c = 0; c <= N; c++) {
if (!board[r][c]) dfs(r, c), cnt++;
}
}
cout << cnt;
}