[BOJ/JAVA] 1780(종이의 개수)

1. Link

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

2. 풀이 과정

1. 3^7은 대략 2000 좀 너머입니다. 즉 2000 * 2000 배열을 전역 변수로 설정한 뒤 배열을 탐색하면 됩니다.
2. 9분할이라 되어있으므로 n / 3 재귀탐색으로 바로 이해 -> 재귀, 분할 정복

• 분할 정복의 일종입니다. 다만 세그먼트 트리처럼 거창한 알고리즘이 필요하기보다는, 재귀에 대한 이해만 있으면 금방 풀 수 있는 문제입니다.

• Java로 간만에 문제를 풀어봤는데, 확실히 C++보다 난이도가 있네요ㅋㅋㅋㅋ 둘 다 적재적소에 사용해보도록 노력해봐야겠어요!

3. 정답 코드

import java.util.Scanner;

public class Main {

    public static int N, ans1 = 0, ans2 = 0, ans3 = 0;
    public static int[][] area = new int[2200][2200];
    public static Scanner sc = new Scanner(System.in);

    public static void input() {
        N = sc.nextInt();
        for (int i = 0; i < N; i++) {
            for (int j = 0;j < N; j++){
                area[i][j] = sc.nextInt();
            }
        }
    }

    public static boolean search(int x, int y, int n){
        int std = area[x][y];
        for(int i = x;i < x + n; ++i){
            for(int j = y;j < y + n; ++j){
                if(area[i][j] != std){
                    return false;
                }
            }
        }
        switch (std){
            case -1:
                ++ans1;
                break;
            case 0:
                ++ans2;
                break;
            case 1:
                ++ans3;
        }
        return true;
    }

    public static void dfs(int x, int y, int n) {
        boolean isSame = search(x, y, n);
        //만약 같을 경우에는 반환
        if(n == 0 || isSame) return;
        int div = n / 3;
        for (int i = x; i < x + n; i+=div) {
            for (int j = y;j < y + n; j+=div){
                dfs(i, j, div);
            }
        }
    }

    public static void main(String[] args) {
        input();
        dfs(0, 0, N);
        System.out.println(ans1);
        System.out.println(ans2);
        System.out.println(ans3);
    }
}

4. 추천 음악

Chasing Fire - Lauv
Link: https://www.youtube.com/watch?v=o-BODsf2T68

풀다가 답답해서 노래 좀 듣고 했는데, 이 노래 생각보다 좋더라고요?
흘러흘러 여기 들어오신 분들께 추천드리는 음악입니다!