[Java] 백준 1780 종이의 개수

 

 

문제

잘라진 종이가 한 숫자로만 이루어져 있는지를 검사하고

그렇다면 종이 개수를 추가하고, 아니라면 9등분으로 나눠 다시 종이 내의 숫자를 검사하는 문제이다.

9등분으로 나누는 부분을 재귀로 처리하였다. 

 

 

풀이

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

public class Main {
    static int N;
    static int[][] map;
    static int[] res;

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

    static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

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

        res = new int[3];
        recursion(0, 0, N);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 3; i++) {
            sb.append(res[i]).append("\n");
        }
        System.out.println(sb);
    }

    static void recursion(int x, int y, int len) {
        boolean isSame = true;
        int number = map[x][y];
        loop:
        for (int i = x; i < x + len; i++) {
            for (int j = y; j < y + len; j++) {
                if (map[i][j] != number) {
                    isSame = false;
                    break loop;
                }
            }
        }
        if (isSame) {
            res[number + 1]++;
            return;
        }

        int nlen = len / 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                recursion(x + i * nlen, y + j * nlen, nlen);
            }
        }
    }
}

 

 

피드백

- 정사각형 형태이고 9등분으로 나누면 너비와 높이 모두 같은 비율로 줄어들기 때문에, nx와 ny를 굳이 나눠서 계산할 필요 없다. nlen = len/3으로 모두 처리 가능

 

 

채점결과