알고리즘 |
그리디 알고리즘 |
[문제 본문]
더보기
문제
0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.
행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 → 1, 1 → 0)
입력
첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.
출력
첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.
예제 입력 1
3 4 0000 0010 0000 1001 1011 1001
예제 출력 1
2
예제 입력 2
3 3 111 111 111 000 000 000
예제 출력 2
1
예제 입력 3
1 1 1 0
예제 출력 3
-1
예제 입력 4
18 3 001 100 100 000 011 010 100 100 010 010 010 110 101 101 000 110 000 110 001 100 011 000 100 010 011 100 101 101 010 001 010 010 111 110 111 001
예제 출력 4
7
[푼 코드]
#include <iostream>
using namespace std;
int N, M;
int arr[51][51];
int goal[51][51];
int Solved()
{
bool isCheck = false;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (arr[i][j] != goal[i][j])
{
isCheck = true;
break;
}
}
if (isCheck) break;
}
if (!isCheck)
return 0;
if (N < 3 || M < 3)
{
return -1;
}
int result = 0;
for (int i = 0; i < N-2; i++)
{
for (int j = 0; j < M-2; j++)
{
if (arr[i][j] != goal[i][j])
{
for (int k = i; k <= i + 2; k++)
{
for (int q = j; q <= j + 2; q++)
{
arr[k][q] = !arr[k][q];
}
}
result++;
}
}
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (arr[i][j] != goal[i][j])
{
return -1;
}
}
}
return result;
}
int main()
{
ios::sync_with_stdio(false);
cout.tie();
cin.tie();
cin >> N >> M;
for (int i = 0; i < N; i++)
{
string str;
cin >> str;
for (int j = 0; j < M; j++)
{
arr[i][j] = str[j] - '0';
//scanf("%1d", &arr[i][j]);
}
}
for (int i = 0; i < N; i++)
{
string str;
cin >> str;
for (int j = 0; j < M; j++)
{
goal[i][j] = str[j] - '0';
//scanf("%1d", &goal[i][j]);
}
}
cout << Solved() << "\n";
return 0;
}
1%에서 계속 오류가 발생했고 원인도 알 수가 없어서 고생을 좀 했습니다..
입력 부분 문제였던 것 같네요 scanf로 안 하고 스트링으로 받아와서 계산해주니 해결되었습니다.
cin.tie를 사용하면 scanf, printf, getchar와 같은 c의 기본 입출력 함수들이 정상 작동하지 않는다고 합니다.
C++의 버퍼와 C의 버퍼 동기화를 끊고 별개로 독립시키기 때문이라고 합니다.
#그리디 알고리즘 #백준 그리디 #백준 1080 #알고리즘
728x90
반응형
'알고리즘 > 백준 알고리즘 공부' 카테고리의 다른 글
[플로이드–와샬] (백준 2458) 키 순서 (0) | 2022.03.15 |
---|---|
[플로이드–와샬] (백준 2660) 회장뽑기 (0) | 2022.03.15 |
[다익스트라] (백준 9370) 미확인 도착지 (0) | 2022.03.15 |
[다익스트라] (백준 4485) 녹색 옷 입은 애가 젤다지? (0) | 2022.03.14 |
[다익스트라] (백준 5972) 택배 배송 (0) | 2022.03.14 |