백준 1780번 종이의 개수

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

1780번: 종이의 개수

 

문제

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

 

입력

첫째 줄에 N(1≤N≤3^7, N은 3^k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

 

출력

첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

 

풀이

분할 정복 문제이다.

 

1. 종이 안에 있는 숫자들이 모두 같으면 종이를 하나로 취급하고

2. 아니면 9등분해서 잘린 종이들에 대해서 다시 반복한다. -> 분할

 

이 문제는 입력 값으로 주어지는 n이 3^k 꼴이므로 쉽게 패턴을 파악할 수 있다.

가장 먼저, 종이 안의 모든 수가 같은지 확인하고

같지 않으면 재귀호출을 통해 종이를 나누면 된다.

 

소스코드

#include <iostream>
using namespace std;
 
int ans[3];  // -1 0 1
int mat[2500][2500];
void cut_paper(int y, int x, int k) {
    if (k == 0) {
        ans[mat[y][x] + 1] += 1;
        return;
    }
    int check = 1;
    int squad = 1;
    for (int i = 0; i < k - 1; i++) { //n/3 구하기
        squad *= 3;
    }
    int t = 3 * squad;
    for (int i = 0; i < t; i++) {
        for (int j = 0; j < t; j++) {
            if (mat[y][x] != mat[y+i][x+j]) check = 0;
        }
    }
    if (check == 0) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                cut_paper(y + i * squad, x + j * squad, k - 1);
            }
        }
    }
    else {
        ans[mat[y][x] + 1] += 1;
    }
}
int main()
{
    int n; scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &mat[i][j]);
        }
    }
    int k = 0; //n이 3의 몇 제곱인지?
    int temp_n = n;
    while (temp_n != 1) {
        temp_n /= 3;
        k++;
    }
    cut_paper(0, 0, k);
    for (int i = 0; i < 3; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}

재귀 함수의 인자로 y, x값과 3의 제곱 수를 넘겼다. 나는 이런 재귀를 풀 때 그냥 제곱 수를 넘기는 게 편해서 그렇게 했는데 다른 분들은 어떨지 모르겠다.

 

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~