백준 1780번 - 종이의 개수

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

1780번: 종이의 개수

 

 

 

 

 

분할정복&재귀 문제이다. 지금까지 풀었던 분할정복 문제 중에서는 쉬운 축에 속하는 것 같다. 재귀에 약해서 쫄았는데 생각보다 금방 풀렸다.

 

 

 

 

 

 

종이의 시작점의 행 번호, 열 번호, 종이의 크기를 매개변수로 보내 종이가 같은 수로 이루어져 있는지 확인한다.

 

종이가 같은 수로 이루어져 있으면, 해당 수의 카운터를 올리고 종료한다.

같은 수로 이루어져 있지 않으면, 재귀를 통해 크기를 1/3로 줄여 9가지의 종이의 시작점에서 다시 탐색한다.

 

 

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class NumberOfPaper {
	static int[] count;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		int[][] arr = new int[N][N];

		for(int i = 0; i < N; i++) {
			String[] input = br.readLine().split(" ");
			
			for(int j = 0; j < N; j++) {
				arr[i][j] = Integer.parseInt(input[j]);
			}
		}
		
		count = new int[3];
		
		paper(arr, 0, 0, N);
		
		System.out.println(count[0]);
		System.out.println(count[1]);
		System.out.println(count[2]);
	}

	public static void paper(int[][] arr, int x, int y, int n) {
		int num = arr[x][y];
		boolean isSame = true;
		
		for(int i = x; i < x + n; i++) {
			for(int j = y; j < y + n; j++) {
				if(arr[i][j] != num) {
					isSame = false;
					break;
				}
			}
		}
		
		if(isSame) {
			if(num == -1) {
				count[0]++;
			} else if(num == 0) {
				count[1]++;
			} else if(num == 1) {
				count[2]++;
			}
			
			return;
		} else {
			paper(arr, x, y, n / 3);
			paper(arr, x, y + n / 3, n / 3);
			paper(arr, x, y + n / 3 * 2, n / 3);
			paper(arr, x + n / 3, y, n / 3);
			paper(arr, x + n / 3, y + n / 3, n / 3);
			paper(arr, x + n / 3, y + n / 3 * 2, n / 3);
			paper(arr, x + n / 3 * 2, y, n / 3);
			paper(arr, x + n / 3 * 2, y + n / 3, n / 3);
			paper(arr, x + n / 3 * 2, y + n / 3 * 2, n / 3);
		}
		
	}

}

 

 

 

 

 

결과

 

 

수행시간이 꽤 크다.. 그래서 내가 비효율적으로 잘못 풀었나 하는 생각이 들었는데 채점현황을 보니 다른 사람들도 기본 1000ms 넘게 나온다. 다행이다😅

 

 

 

 

 

참고

스스로 풀어서 없음