[java백준] 실버 2/ 1780번 종이의 개수

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

1780번: 종이의 개수

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int n;
    public static int m;
    public static int[][] arr;
    public static int[] totalNum = new int[3];
 
    public static boolean check(int row, int col, int n) {
        int standard = arr[row][col];
        for (int i = row; i < row + n; i++) {
            for (int j = col; j < col + n; j++) {
                if (standard != arr[i][j]) {
                    return false;
                }
            }
 
        }
        return true;
    }
 
    public static void divide(int row, int col, int n) {
        if (check(row, col, n)) {
            totalNum[arr[row][col] + 1]++;
        } else {
            // 분할
            int num = n / 3;
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    divide(row + (i * num), col + (j * num), num);
                }
            }
        }
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        arr = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        divide(1, 1, n);
        for (int i = 0; i < 3; i++) {
            System.out.println(totalNum[i]);
        }
    }
 
}

 

분할정복을 이용해서 풀면 된다.

메서드가 두가지 필요한데, 한 가지는 배열을 쪼개주는 메서드 하나는 배열의 모든 원소가 같은 원소인지 판단해주는 메서드이다.

 

divide가 배열을 쪼개주는 메서드인데

if (check(row, col, n)) {

            totalNum[arr[row][col] + 1]++;

        } 

--> 만약 모두 같은수라면 상관이 없지만

else {

            // 분할

            int num = n / 3;

            for (int i = 0; i < 3; i++) {

                for (int j = 0; j < 3; j++) {

                    divide(row + (i * num), col + (j * num), num);

                }

            }

        }

--> 하나라도 다른 수가 있다면 종이를 쪼개줘야한다.

이때 3으로 나누는건 어차피 n이 3의 제곱수이기 때문에 분할을 할때 항상 3으로 나누게 된다.

 

 

참고한 사이트

https://developer-mac.tistory.com/38

[Java]백준 1780번 :: 종이의 개수