문제
https://www.acmicpc.net/problem/25682
풀이
시간초과 (이중 반복문)
#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
/**
어느 위치에서 KxK 보드를 만들어야
다시 칠해야 하는 칸의 개수를 최소화 할 수 있는가?
그때 칸의 개수는?
*/
const int MAX = 2001;
char arr[MAX][MAX];
char black[MAX][MAX];
char white[MAX][MAX];
int N, M, K; // N행 M열
int ans = 1e9;
void initChessBoards(){
/*
BWBWB (0, 0) (0, 2) (0, 4)
WBWBW (1, 1) (1, 3)
BWBWB (2, 0) (2, 2) (2, 4)
WBWBW (3, 1) (3, 3)
BWBWB
*/
for(int i = 0; i < K; i++){
for(int j = 0; j < K; j++){
if(i % 2 == 0){
if(j % 2 == 0){
black[i][j] = 'B';
}else{
black[i][j] = 'W';
}
}else{
if(j % 2 != 0){
black[i][j] = 'B';
}else{
black[i][j] = 'W';
}
}
}
}
for(int i = 0; i < K; i++){
for(int j = 0; j < K; j++){
if(i % 2 == 0){
if(j % 2 == 0){
white[i][j] = 'W';
}else{
white[i][j] = 'B';
}
}else{
if(j % 2 != 0){
white[i][j] = 'W';
}else{
white[i][j] = 'B';
}
}
}
}
}
int countDiff(int startX, int startY){
int blackMissMatch = 0, whiteMissMatch = 0;
for(int i = startX; i < startX + K; i++){
for(int j = startY; j < startY + K; j++){
if(arr[i][j] != black[i - startX][j - startY]) {
blackMissMatch++;
}
}
}
for(int i = startX; i < startX + K; i++){
for(int j = startY; j < startY + K; j++){
if(arr[i][j] != white[i - startX][j - startY]) {
whiteMissMatch++;
}
}
}
return min(blackMissMatch, whiteMissMatch);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M >> K;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
cin >> arr[i][j];
}
}
initChessBoards();
for(int i = 0; i < N; i++){
if(i + K > N) continue;
for(int j = 0; j < M; j++){
if(j + K > M) continue;
ans = min(ans, countDiff(i, j));
}
}
cout << ans;
return 0;
}N, M, K의 최댓값은 2000이다. 따라서 O(N^2)까지는 가능하지만 그 이상은 시간초과가 발생한다.
countDiff 함수에서 KxK 크기의 보드 전체를 이중 반복문으로 순회하기 때문에, 시간복잡도가 O(N * M * K^2)까지 커져서 타임아웃이 발생한다.
이중 반복문으로 두 배열의 원소를 비교하면, 불가피하게 O(N^2)의 시간복잡도가 걸린다.
이보다 더 효율적으로 두 배열에서 서로 다른 원소의 개수를 구하는 방법이 없을까??
2차원 누적합 배열을 미리 만들어두고, O(1)의 시간복잡도로 구간 합을 구하는 방법이 있다!
(1, 1) ~ (i, j) 영역의 누적 합 dp[i][j]
→ dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + arr[i][j]
(i - K, j - K) ~ (i, j) 영역의 구간 합
→ dp[i][j] - dp[i - K][j] - dp[i][j - K] + dp[i - K][j - K]
구간 합
#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
/**
어느 위치에서 KxK 보드를 만들어야
다시 칠해야 하는 칸의 개수를 최소화 할 수 있는가?
그때 칸의 개수는?
BWBWB (0, 0) (0, 2) (0, 4)
WBWBW (1, 1) (1, 3)
BWBWB (2, 0) (2, 2) (2, 4)
WBWBW (3, 1) (3, 3)
(i + j) 짝수 -> (0, 0)과 동일 색상이어야 함.
(i + j) 홀수 -> (0, 0)과 반대 색상이어야 함.
*/
int N, M, K; // N행 M열
int checkRepaint(char startColor, char inputColor, int row, int col){
if((row + col) % 2 == 0){
return inputColor != startColor;
}else{
return inputColor == startColor;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int ans = 1e9;
cin >> N >> M >> K;
// (1, 1) ~ (i, j) 영역을 체스판 모양으로 만들기 위해
// 다시 칠해야 하는 칸 수의 누적합
// 1 <= i <= N, 1 <= j <= M
vector<vector<int>> bsum(N + 1, vector<int>(M + 1, 0));
vector<vector<int>> wsum(N + 1, vector<int>(M + 1, 0));
for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++){
char color;
cin >> color;
bsum[i][j] = bsum[i - 1][j] + bsum[i][j - 1] - bsum[i - 1][j - 1] + checkRepaint('B', color, i, j);
wsum[i][j] = wsum[i - 1][j] + wsum[i][j - 1] - wsum[i - 1][j - 1] + checkRepaint('W', color, i, j);
}
}
// (i - K, j - K) ~ (i, j) 영역에 대한 구간 합
// K <= i <= N, K <= j <= M
int minBlackCase = 1e9, minWhiteCase = 1e9;
for(int i = K; i <= N; i++){
for(int j = K; j <= M; j++){
int blackCase = bsum[i][j] - bsum[i][j - K] - bsum[i - K][j] + bsum[i - K][j - K];
int whiteCase = wsum[i][j] - wsum[i][j - K] - wsum[i - K][j] + wsum[i - K][j - K];
minBlackCase = min(minBlackCase, blackCase);
minWhiteCase = min(minWhiteCase, whiteCase);
}
}
cout << min(minBlackCase, minWhiteCase);
return 0;
}
참고자료
습관이 될 때까지 📝