Search
Duplicate

행렬

주차
0
문제번호
1080
언어
티어
실버
유형
그리디
nj_Blog
nj_상태
이해도
풀이
사람
이해도 2
13 more properties

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++
복사