https://www.acmicpc.net/problem/25682
25682번: 체스판 다시 칠하기 2
첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.
www.acmicpc.net
2차원 배열 내 누적합 문제입니다.
2차원 누적합은 (sx, sy) ~ (ex, ey)의 누적합을 말하며, dp[i][j] = cur + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] 공식을 활용해야 합니다.
체스판은 검은색, 흰색이 번갈아 칠해져있어야 하고, (1, 1) 지점의 색은 정해지지 않았습니다.
따라서 (1, 1) 지점에 검은색이 올 경우와 흰색이 올 경우를 모두 구해서 최솟값을 구해야 합니다.
이를 위해 dp를 두개 사용합니다.
좌표의 x, y값을 더한 값이 홀수인 좌표들끼리와 짝수인 좌표들끼리의 색은 같습니다.
이를 활용하여 해당 좌표에 색이 바껴야하는지에 대해서 각각 누적합을 구할 수 있습니다.
dp를 채웠다면 K * K 크기의 정사각형의 누적합들을 순회하며 최솟값을 구하도록 합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
#include <iostream>
#include <algorithm>
#define MAX 2001
using namespace std;
char list[MAX][MAX];
int bdp[MAX][MAX], wdp[MAX][MAX];
int N, M, K;
void getPrefixSum() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
bdp[i][j] = bdp[i - 1][j] + bdp[i][j - 1] - bdp[i - 1][j - 1];
wdp[i][j] = wdp[i - 1][j] + wdp[i][j - 1] - wdp[i - 1][j - 1];
if (list[i][j] == 'W') {
if ((i + j) % 2) {
wdp[i][j]++;
}
else {
bdp[i][j]++;
}
}
else {
if ((i + j) % 2) {
bdp[i][j]++;
}
else {
wdp[i][j]++;
}
}
}
}
}
void func() {
getPrefixSum();
int ret = 2147483647;
for (int i = K; i <= N; i++) {
for (int j = K; j <= M; j++) {
ret = min(ret, bdp[i][j] - bdp[i - K][j] - bdp[i][j - K] + bdp[i - K][j - K]);
ret = min(ret, wdp[i][j] - wdp[i - K][j] - wdp[i][j - K] + wdp[i - K][j - K]);
}
}
cout << ret << '\n';
}
void input() {
cin >> N >> M >> K;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cin >> list[i][j];
}
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 12841 정보대 등산 (0) | 2023.07.31 |
|---|---|
| boj 25427 DKSH를 찾아라 (0) | 2023.05.21 |
| boj 12996 Acka (0) | 2023.01.29 |
| boj 14450 Hoof, Paper, Scissors (Gold) (0) | 2022.12.30 |
| boj 14453 Hoof, Paper, Scissors (Silver) (0) | 2022.12.30 |