이번 문제는 그리디 알고리즘을 통해 쉽게 해결하였다. 동전을 뒤집을 경우, 현재 좌표 이하의 모든 좌표가 함께 뒤집히기 때문에 뒤집는 횟수를 최소로 하기 위해서는 같은 동전의 뒤집히는 횟수가 최소가 되어야 한다. 그렇기 때문에 가장 큰 좌표부터 확인해가며 현재 좌표가 1일 경우 뒤집기를 수행하도록 구현하였다.

Code

n, m = map(int, input().split())
coins = [list(str(input())) for _ in range(n)]
for i in range(n):
    for j in range(m):
        coins[i][j] = int(coins[i][j])
answer = 0
for i in range(n-1, -1, -1):
    for j in range(m-1, -1, -1):
        if coins[i][j] == 1:
            answer += 1
            for k in range(i+1):
                for l in range(j+1):
                    coins[k][l] = not coins[k][l]
        if coins == [[0 for _ in range(m)] for _ in range(n)]:
            print(answer)
            quit()