백준 1455 뒤집기 2

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

 

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> arr;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    int n, m;
    int ans = 0;

    cin >> n >> m;

    arr.resize(n, vector<int>(m));

    for (int i = 0; i < n; i++) {
        string temp;
        cin >> temp;

        for (int j = 0; j < m; j++) {
            arr[i][j] = temp[j] - '0';
        }
    }

    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            if (arr[i][j] == 1) {
                ans++;
                for (int k = 0; k <= i; k++) {
                    for (int l = 0; l <= j; l++) {
                        arr[k][l] = 1 - arr[k][l];
                    }
                }

            }
        }
    }

    cout << ans;


    return 0;
}

1. 문제

n*m으로 이루어진 동전의 배열이 앞면은 0, 뒷면은 1로 주어진다. (a, b) 위치의 동전을 뒤집으면 (0~a, 0~b)에 해당하는 모든 동전이 뒤집어지고, 이를 연산 한 번으로 간주한다. 이 때, 모든 동전을 앞면으로 바꾸기 위한 최소 횟수를 구하라.

2. 풀이

가장 많이 동전을 뒤집을 수 있는 우측 최하단부터 그리디하게 체크한다. 동전이 뒷면일 경우 연산을 수행해나간다.

for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            if (arr[i][j] == 1) {
                ans++;
                for (int k = 0; k <= i; k++) {
                    for (int l = 0; l <= j; l++) {
                        arr[k][l] = 1 - arr[k][l];
                    }
                }

            }
        }
    }

동전이 뒷면일 경우 문제에서 정의된 대로 좌측 최상단부터 현재 위치까지의 모든 동전을 뒤집는다. 한번 연산을 했을 때 연산 범위 내의 동전이 앞면이 되면 그 동전은 그대로 둬도 되고, 뒷면이 되면 어짜피 뒤집어야 하므로 연산의 횟수를 계산해서 늘려야 한다. 

 위 연산 후 ans를 출력하면 정답을 구할 수 있다.