1780번 종이의 개수

문제

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

 

 

---

문제 풀이

 

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static int [] count = new int[3];
	public static int arr [][];
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(bf.readLine());
		arr = new int[n][n];
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(bf.readLine());
			for (int j = 0; j < n; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				
			}
		}
		partition(0,0,n);
		
		for(int a : count) {
			sb.append(a).append("\n");
		}
		System.out.println(sb.toString());
	}
	public static void partition(int row, int col, int size) {
		if(check(row,col,size)) {
			count[arr[row][col]+1]++;
			return;
		}
				
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				partition(row + size/3 * i, col + size/3 * j, size/3);	
			}
		}
		
	}
	public static boolean check(int row, int col, int size) {
		int start = arr[row][col];
		for (int i = row; i < row + size; i++) {
			for (int j = col; j < col + size; j++) {
				if (start != arr[i][j]) {
					return false;
				}
			}
		}
		return true;
	}

}

• 어제 풀었던 문제와 비슷한 문제! 확실히 분할 정복 문제에 대한 감이 잡힌거 같다!