[C++] 백준 1780 - 종이의 개수

www.acmicpc.net/problem/1780

1780번: 종이의 개수

<풀이>

1. 정사각형 종이의 한 변 크기인 N과 종이의 모양을 입력받는다.

2. 해당 종이를 지정한 방식으로 잘랐을 때, 각 종류별 종이의 개수를 출력한다.

 

<해법>

1. 자르는 방식을 분석하는 방법

=> 주어진 종이를 9부분으로 나누고 같은 방식으로 종이를 계속 잘라 나갑니다. 여기서 분할 정복을 사용해야 한다는 생각을 할 수 있습니다. 각 부분마다 같은 숫자가 쓰여져 있는지 확인하고, 아닌 경우 계속 잘라나가는 방식으로 구현하였습니다.

 

#include <iostream>
#include <string.h>
 
using namespace std;
 
int N;
int map[2200][2200];
//[0]:-1종이 개수, [1]:0종이 개수, [2]:1종이 개수
int answer[3];
 
//모두 같은 숫자인지 판단
bool allSameNumber(int x, int y, int n) {
    
    int check = map[x][y];
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map[x + i][y + j] != check) {
                return false;
            }
        }
    }
 
    return true;
}
 
void makePaper(int x, int y, int n) {
 
    //종이가 모두 같은 숫자일 경우 -> 해당 종이 갯수 + 1, 종료
    if (allSameNumber(x, y, n)) {
        int paperNum = map[x][y];
        answer[paperNum + 1]++;
        return;
    }
 
    int div = n / 3;
 
    //9개로 나누어서 분할 정복
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            makePaper(x + div * i, y + div * j, div);
        }
    }
}
 
int main() {
 
    //초기화
    N = 0;
    memset(map, 0, sizeof(map));
    memset(answer, 0, sizeof(answer));
 
    //입력
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
 
    //해법
    /*
    9개로 나누어서 분할 정복
    */
    makePaper(0, 0, N);
 
    //출력
    for (int i = 0; i < 3; i++) {
        cout << answer[i] << "\n";
    }
 
    //종료
    return 0;
}

 

분할 정복에 대해 알아볼 수 있는 문제였습니다.