[백준 1780] 종이의 개수 - JAVA

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

 

분할 정복 문제

 

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

class Main {

  static int N, qa, wa, ea;
  static int[][] m;

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

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

    m = new int[N][N];
    for (int i = 0; i < N; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < N; j++) {
        m[i][j] = Integer.parseInt(st.nextToken());
      }
    }

    solve(0, N, 0, N, N);
    System.out.print(String.format("%d%n%d%n%d", qa, wa, ea));
  }

  static void solve(int sr, int er, int sc, int ec, int line) {

    int q = 0;
    int w = 0;
    int e = 0;

    for (int r = sr; r < er; r++) {
      for (int c = sc; c < ec; c++) {
        if (m[r][c] == -1) {
          q++;
        } else if (m[r][c] == 0) {
          w++;
        } else {
          e++;
        }
      }
    }

    int square = line * line;
    if (q == square) {
      qa++;
      return;
    } else if (w == square) {
      wa++;
      return;
    } else if (e == square) {
      ea++;
      return;
    }

    int l = line / 3; // 좌표 나눌 간격

    for (int r = sr; r < er; r += l) {
      for (int c = sc; c < ec; c += l) {
        solve(r, r + l, c, c + l, l);
      }
    }
  }
}