본문 바로가기
알고리즘/분할정복

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

by Meaning_ 2022. 1. 28.
728x90
반응형

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

 

1780번: 종이의 개수

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수

www.acmicpc.net

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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(11, n);
        for (int i = 0; i < 3; i++) {
            System.out.println(totalNum[i]);
        }
    }
 
}
cs

 

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

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

 

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번 :: 종이의 개수

백준 온라인 저지 1780번 '종이의 개수' Java 알고리즘 문제풀이 풀이 이 문제는 분할정복(Divide and Conquer)로 풀면된다. 분할정복은 정말 쉬운 개념이다. (유사한 분할정복 문제 풀기 -> 백준 1992번 쿼

developer-mac.tistory.com

 

728x90
반응형

댓글