[백준] 1780. 종이의 개수 (자바 JAVA)

[ 문제 ]  [백준] 1780. 종이의 개수 (자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/1780

1780번: 종이의 개수

---

# 접근 방법 및 풀이 

 

• 재귀문제 중에 정말 좋은 문제라고 생각한다. 그리고 실버2는 아닌거같음.. 실버1~골드5?
• 이전에 백준1992 쿼드트리를 풀고나면 접근방법은 쉽다.
  • https://ilmiodiario.tistory.com/137
• 문제 그대로 재귀 짜면 된다. 그러나 주의할 점이 좀 있다.
• 조건 1에 "만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다." 라고 되어있으므로, 재귀 return 조건이 된다. 그리고 모두 같은 수로 되어있는지 체크하는 함수를 만들어야한다.
• 따라서 재귀함수 solve(), 모두 같은 수로 되어있는지 체크하는 check() 두개의 함수를 만들었다.
• 먼저, check함수는 시작 행 r 열 c와 size를 파라미터로 입력받아 map[r][c] 부터 size까지 이중for문으로 체크해서 모두 같은수라면 true, 같은 수가 아니라면 false를 반환한다.
• 처음엔 문제를 제대로 안 봐서 9개의 숫자가 모두 같은 숫자여야지만 종이라고 생각하고 그때 카운팅해줬는데 그게 아니다.
• 하나의 종이를 9분할로 계속해서 잘라서 종이에 적힌 수가 다 같을 경우에, 그적힌 숫자의 카운트를 세야한다.
• 여기서 하나의 종이라는 개념을 잘 생각해야한다. 종이마다 사이즈가 다를 수 있다.
• 하나의 종이를 계속해서 9분할을 해주면, 
• 3x3 사이즈의 종이가 있을 수도 있고
  

  0	0	0
  0	0	0
  0	0	0

•  1X1 사이즈의 종이가 있을 수 있다.

  0

• 둘다 하나의 종이고, 사이즈만 다를 뿐이다. 입력에 N은 (1 ≤ N ≤ 3^7)형태로 주어지므로 N = 27일 경우, 27X27, 9X9, 3X3, 1X1 사이즈의 종이가 있을 수 있다.
• 이렇게 문제를 이해했다면, 조건1에 모두 같은 숫자로 되어있다면 이 종이 그대로 사용한다고 했으므로, 그때 종이에 적힌 숫자대로 카운트를 세주면 된다.
• 그게 아닐 경우 이중 for문으로 종이를 9분할해 새로운 r, c, size를 정해서 재귀를 돌리면된다. 이때 size는 / 3 을한 사이즈다. 
• 자세한건 코드참조 

# 주의할 점 

 

• 문제 제대로 이해하기

 

JAVA 코드

package Silver;

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

public class bj1780_종이의개수 {

	static int N, map[][], zero = 0, one = 0, minus = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		map = new int[N][N];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(in.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		solve(0, 0, N);
		System.out.println(minus);
		System.out.println(zero);
		System.out.println(one);
	}
	private static void solve(int r, int c, int size) {
		if(check(r, c, size)) {
			int num = map[r][c];
			if(num == 0)
				zero++;
			if(num == 1)
				one ++;
			if(num == -1)
				minus ++;
			return;
		}
		
		int newSize = size / 3;
		for (int i = r; i < r+size; i+= newSize) {
			for (int j = c; j < c+size; j += newSize) {
				solve(i, j, newSize);
			}
		}	
	}
	
	private static boolean check(int r, int c, int size) {
		for (int i = r; i < r + size; i++) {
			for (int j = c; j < c + size; j++) {
				if(map[r][c] != map[i][j])
					return false;
			}
		}

		return true;
	}
}

 

 

 

REVIEW