[백준 1455] 뒤집기 II - JAVA

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

 

그리디

 

1. (i,j)를 뒤집으면 (0,0) ~ (i,j)가 같이 뒤집히므로, 최외곽부터 뒤집는게 무조건 최적

2. 동전을 모두 앞면으로 만들지 못하는 경우는 없으므로 뒷면이 없으면(one == 0) 종료

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());

    int one = 0;
    int zero = 0;

    boolean[][] m = new boolean[N][M];

    for (int i = 0; i < N; i++) {
      String s = br.readLine();
      for (int j = 0; j < M; j++) {

        if (s.charAt(j) == '0') {
          zero++;
        } else {
          one++;
          m[i][j] = true;
        }
      }
    }

    int flip = 0;

    // 1 == 뒷면 == true
    for (int i = N - 1; i >= 0; i--) {
      for (int j = M - 1; j >= 0; j--) {

        if (m[i][j]) {
          flip++;

          for (int k = 0; k <= i; k++) {
            for (int l = 0; l <= j; l++) {

              // 뒷면이면
              if (m[k][l]) {
                one--;
                zero++;
                m[k][l] = false;
              } else {
                one++;
                zero--;
                m[k][l] = true;
              }
            }
          }
        }

        if (one == 0) {
          System.out.println(flip);
          return;
        }
      }
    }

  }
}