백준 1780 종이의 개수 c++ [컴공과고씨]

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

1780번: 종이의 개수

문제 유형을 보고 분할정복을 떠올려 풀어준 문제이다.

각 변을 3씩 나누면서 보면 탐색하는 문제이다.

보면 처음에 9로 시작한다. 모든 원소가 같지 않다면 n/3으로 나누고 각 분면의 시작 좌표로 이동해주어야한다. 

​이런식의 좌표가 나온다. y가 행 x는 열.

 

 

단계별 풀이

1. 입력을 받아주고 papper 재귀함수로 들어간다.

2. bool 변수 선언 후 각 분면에 있는 원소들을 탐색해서 하나라도 다르면 bool 변수에 false를 저장

3. 만약 원소가 다른게 있었다면 9개로 잘라서 9분면에 넣어줌

4. 만약 모두 같다면 원소가 그 원소 수를 저장하는 변수에 +1을 해줌

 

전체코드

#include <iostream>
#include <cmath>
using namespace std;
int n;
int one = 0;
int m_one = 0;
int ze = 0;
int map[2200][2200];
void papper(int x, int y, int size){
    bool same = true;
    for (int i = y; i < y+size;i++){ //각 분면 탐색
        for (int j = x; j < x + size;j++){
            if(map[i][j] != map[y][x]){
                same = false; // 원소 하나라도 다르면 false
                break;
            }
        }
        if(!same){
            break;
        }
    }
    if(!same){
        papper(x, y, size / 3); // 1번
        papper(x+size/3, y, size / 3); // 2번
        papper(x+size/3+size/3, y, size / 3); // 3번
        papper(x, y+size/3, size / 3); // 4번
        papper(x, y+size/3+size/3, size / 3); // 7번
        papper(x+size/3, y+size/3, size / 3); // 5번
        papper(x+size/3+size/3, y+size/3+size/3, size / 3); // 9번
        papper(x+size/3, y+size/3+size/3, size / 3); // 8번
        papper(x+size/3+size/3, y+size/3, size / 3); // 6번
    }else{
        if(map[y][x] == 1){
            one++; // 1인 경우
        }else if(map[y][x] == -1){
            m_one++; // -1인 경우
        }else{
            ze++; // 0인 경우
        }
    }
}
 
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n;i++){
        for (int j = 0; j < n;j++){
            cin >> map[i][j];
        }
    }
    papper(0, 0, n);
    cout << m_one << '\n';
    cout << ze << '\n';
    cout << one << '\n';
    return 0;
}// 28min

난이도	걸린시간	참고	사용 알고리즘
하	28min	x	분할정복