<Algorithm> 188. 종이의 개수(BJO)

1. 1780번 종이의 개수(BJO)

   사용 알고리즘 : 분할정복 

• 갑자기 분할정복 문제를 풀어야겠다는 생각이 들어서 이걸 풀어보았다. 역시 전혀 기억이 나지않았다..(뭐든지 확실하게 이해해둬야겠다.)

• 단순이 구현으로 풀수있는 문제이지만 간결하지 못할 것 같다는 생각이 들었고 다른 블로그를 참고하면서 풀어보았다.

• 분할정복의 큰 틀은 체크하고 분할하고 체크하고 분할하고의 반복인데 분할이 0.0 기준으로 이루어진다는게 핵심포인트이다.

• 즉 27 -> 9 -> 3 -> 1 0.0 기준으로 분할하고 오른쪽 0.1이 실행된다. 

문제에 대한 접근&생각

1. 배열을 분할해서 분할된 배열의 값이 일치해야함 -> 분할정복!

내 코드 

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 59 60 61 62 63 64 65 66

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class Main {     static int n,zero,mone,pone;     static int[][] map;          public static void main(String[] args) throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         n = Integer.parseInt(br.readLine());         /***************************          * 배열을 9등분 하면서 탐색한다.          * 예를들어(n기준) 27 -> 9 -> 3          * 하나의 숫자로 이루어저있는지 체크          * 이후에 맞으면 종료, 아니면 9등분          * 을 반복한다.           ***************************/         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());             }         }         solve(0, 0, n);         System.out.println(mone);         System.out.println(zero);         System.out.println(pone);              }          private static void solve(int x, int y, int n) {                  if(isPaper(x, y, n)) {             if(map[x][y] == -1) {                 mone++;             }else if(map[x][y] == 0) {                 zero++;             }else {                 pone++;             }             return;         }                  int div = n/3;                  for(int i = 0; i < 3; i++) {             for(int j = 0; j < 3; j++) {                 solve(x+i*div, y+j*div, div);             }         }              }     private static boolean isPaper(int x, int y, int n) {         for(int i = x; i < x+n; i++) {             for(int j = y; j < y+n; j++) {                 if(map[x][y] != map[i][j])                      return false;             }         }         return true;     } }   Colored by Color Scripter

cs

 

참고 & 출처  

https://wjdgus2951.tistory.com/57