[BOJ] 1455번_뒤집기 II_그리디

[문제]

https://www.acmicpc.net/problem/1455

NxM 크기의 직사각형에 동전이 차곡차곡 놓여져 있다. 동전의 앞면을 0 뒷면을 1이라고 했을 때, 모든 동전을 뒤집어서 앞면으로 만들려고 한다.

(a,b)칸에 있는 동전을 뒤집으려고 하면 (i,j)(1 <= i <= a && 1 <= j <= b)의 조건을 만족하는 axb개의 동전이 모두 뒤집힌다. (i는 위에서 부터, j는 왼쪽에서 부터의 위치이다.)

이 때 뒤집어야하는 동전의 개수를 출력하는 문제이다.

[사용 알고리즘]

그리디

[풀이 핵심]

• 입력값이 붙어있는 숫자이므로 cin이 아닌 scanf_s("%1d", &arr[i][j]);로 입력받아야한다.
• 직사각형의 맨처음인 왼쪽위부터 탐색하면 동전을 뒤집었을 때 다시 맨처음부터 다시 탐색해야하므로, 직사각형의 마지막인 오른쪽아래부터 역순으로 탐색을 하며 동전을 뒤집어야한다.

[코드]

//boj1455번_뒤집기 II_그리디 알고리즘

#include<iostream>

using namespace std;

int arr[101][101];

int main() {
	int N, M;
	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			scanf_s("%1d", &arr[i][j]);
		}
	}

	int result = 0;

	for (int i = N; i > 0; i--) {
		for (int j = M; j > 0; j--) {
			if (arr[i][j] == 1) {
				for (int x = 1; x <= i; x++) {
					for (int y = 1; y <= j; y++) {
						if (arr[x][y] == 1) {
							arr[x][y] = false;
						}
						else {
							arr[x][y] = true;
						}
					}
				}
				result++;
			}
		}
	}

	cout << result;

	return 0;
}