백준 1780번 - 종이의 개수 / Java

문제

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

1780번: 종이의 개수

종이의 개수를 세는문제 큰 배열을 작은 배열로 쪼개가면서 풀면 된다.

문제설명에서 

1. ~~~이 맞다면 ~~~해라

2. ~~~~아니라면 1을해라 

이런식으로 나와있는데 대부분 이런식의 문제는 재귀함수를 활용하면 접근이 쉽다.

1번이 나올때까지 계속들어가다가 1번이나오면 해결하고 차례대로 나오면 되기때문.

 

알고리즘

1. 검사를 시작할 배열의 인덱스를 x,y로 놓고 검사할범위를 n으로 잡는다

2. 검사범위를 n/3만큼 줄여가면서 행렬을 검사한다. 이때 범위n의 숫자가 다같다면 종이의 개수를 세어준다

3. n이 1이될때까지 2를 반복한다. 검사가끝나면 return해서 출력

소스코드

/*
 * BO1780
 * 2020.02.03
 * Hyeonseong
 */
import java.util.*;    
public class BOJ1780 {
    public static void main(String[] args) {
        Solution s = new Solution();
    }
}
class Solution{
    int paper[][];
    int cnt[];
    public Solution() {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        paper = new int[n][n];
        cnt = new int[3];
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                paper[i][j] = scan.nextInt();
            }
        }
        go(0,0,n);
        for(int i=0;i<3;i++) {
            System.out.println(cnt[i]);
        }
    }
    public void go(int x,int y,int n) {
        if(check(x,y,n)) {
            cnt[paper[x][y]+1] += 1;
            return;
        }
        int m = n/3;
        for(int i=0;i<3;i++) {
            for(int j=0;j<3;j++) {
                go(x+i*m,y+j*m,m); // 검사하러 배열을 쪼개서 들어감
            }
        }
    }
    public boolean check(int x, int y, int n) {
        for(int i=x;i<x+n;i++) {
            for(int j=y;j<y+n;j++) {
                if(paper[x][y]!=paper[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
}