[BOJ] 1780 종이의 개수 - JAVA

1. 문제

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

1780번: 종이의 개수

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

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

 

쿼드트리 , 색종이 만들기​ 와 비슷하다.

---

2. 풀이

메인함수

• result는 3칸이다. -1,0,1을 구분해야하기 때문이다. -1인덱스는 존재하지않기때문에 모두 +1을 해주었다.

static int[][] paper;
static int[] result;
public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   StringTokenizer st;

   int N = Integer.parseInt(in.readLine());
   paper = new int[N][N];
   result = new int[3];

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

   cutPaper(0,0,N);

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

   System.out.print(sb);
}

종이 자르는 함수

• 다른건 모두 색종이만들기와 비슷한데 이번에는 분할할 종류가 9가지라 이중for문을 사용했다.

private static void cutPaper(int y, int x, int n) {
   if(n==1 || checkPaper(y,x,n)) {
      result[paper[y][x]+1] ++;
      return;
   }

   int divide = n/3;
   for(int i=y;i<y+n;i+=divide){
      for(int j=x;j<x+n;j+=divide){
         cutPaper(i,j,divide);
      }
   }
}

종이 체크하는 함수

• 이것도 비슷해서 설명하지않겠다.

private static boolean checkPaper(int y, int x, int n) {
   int first = paper[y][x];
   for(int i=y;i<y+n;i++){
      for(int j=x;j<x+n;j++){
         if(first != paper[i][j]) return false;
      }
   }
   return true;
}

---

3. 결과

메모리가 어마어마하게 든다. 역시 9분할이 원인일까?