Memo
•
각 점을 변화 시키기 위해 적어도 한 번은 flip 해주어야 합니다.
•
그 flip의 최소를 구하기 위해서는 0,0 부터 시작하여 x,y를 기준으로 x+2, y+2를 flip시키고, x,y를 N - 2, M - 2 까지 증가해가며 조사해야합니다.
•
이것이 왜 그리디인지 이해가 잘 안되어서 찾아봤는데 매 순간 ‘뒤집어야 하는 칸의 뒤집는 횟수를 최소화한다’는 점에서 그리디 알고리즘으로 분류된다고 합니다. → https://www.acmicpc.net/board/view/13509
Code
제출 날짜
@3/18/2021
메모리
2024 KB
시간
0 ms
#include <iostream>
int N, M;
bool A[51][51];
bool B[51][51];
int ans;
void input_faster()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
input_faster();
std::string tmp;
std::cin >> N >> M;
for (int i = 1 ; i <= N ; i++)
{
std::cin >> tmp;
for (int j = 1 ; j <= tmp.size(); j++)
A[i][j] = tmp[j - 1] - '0';
}
for (int i = 1 ; i <= N ; i++)
{
std::cin >> tmp;
for (int j = 1 ; j <= tmp.size(); j++)
B[i][j] = tmp[j - 1] - '0';
}
ans = 0;
}
bool is_equal()
{
for (int i = 1 ; i <= N; i++)
for (int j = 1; j <= M; j++)
if (A[i][j] != B[i][j])
return (0);
return (1);
}
void flip(int i, int j)
{
for (int x = 0 ; x < 3 ; x++)
{
for (int y = 0 ; y < 3 ; y++)
{
if (A[i + x][j + y])
A[i + x][j + y] = 0;
else
A[i + x][j + y] = 1;
}
}
}
void solve()
{
for (int i = 1 ; i <= N ; i++)
{
for (int j = 1 ; j <= M ; j++)
{
if (i + 2 > N || j + 2 > M)
break;
if (A[i][j] != B[i][j])
{
flip(i, j);
ans++;
}
}
}
if (!is_equal())
ans = -1;
}
void print_val()
{
std::cout << ans;
}
int main()
{
input();
solve();
print_val();
return (0);
}
C++
복사