종이의 개수

📍 문제 설명

💡 접근

N이 3^k 꼴이라는 조건이 주어져서 주어진 예시를 이용해서 풀 수 있었다.

해당 영역의 숫자들이 같은지 판단 후 같다면 종이로 사용해서 끝내고 아니라면 잘라서 다시 판단한다.

 

👩‍💻 코드

import java.util.*;

public class Main {
    static int n, m, h, k, answer,cnt, max, min, red, yellow, orange;
    static int[][] board;
    static int[] dis = {-1,1,2};
    static int[] visited = new int[100001];
    static int[] parent = new int[100001];
    static int[] ch,pm, combi;
    static boolean flag = false;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static HashSet<String> set = new HashSet<>();
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        n = kb.nextInt();
        board = new int[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                board[i][j] = kb.nextInt();
            }
        }
        //1, 3, 2
        //9, 9, 9


        T.solution(0, 0, n);
        System.out.println(red);
        System.out.println(yellow);
        System.out.println(orange);

    }

    private void solution(int x, int y, int size) {

        //해당 지점 같은 색상으로 이루어져 있다면 숫자에 해당하는 색깔 증가
        //1x1 포함 종이를 사용할 수 있으면 더 이상 자르지 않도록 리턴
        if(colorCheck(x, y, size)) {
            if(board[x][y] == -1) red++;
            else if (board[x][y] == 0) yellow++;
            else orange++;
            return;
        }

        //같은 크기의 종이 9개로 자르기
        int newSize = size / 3;

        //위쪽
        solution(x, y, newSize);
        solution(x, y + newSize, newSize);
        solution(x, y + 2 * newSize, newSize);

        //중앙
        solution(x + newSize, y, newSize);
        solution(x + newSize, y + newSize, newSize);
        solution(x + newSize, y + 2 * newSize, newSize);

        //아래쪽
        solution(x + 2 * newSize, y, newSize);
        solution(x + 2 * newSize, y + newSize, newSize);
        solution(x + 2 * newSize, y + 2 * newSize, newSize);

    }

    private boolean colorCheck(int x, int y, int size) {
        int color = board[x][y];

        for(int i = x; i < x + size; i++) {
            for(int j = y; j < y + size; j++) {
                if(color != board[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }


}