[백준] 1780번 종이의 개수

문제: 1780번: 종이의 개수

basic-algo-lecture/workbook/0x0B.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x0B.md at master · encrypted-def/basic-algo-lecture

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>
#include <list>

using namespace std;

int minusCount = 0;
int zeroCount = 0;
int plusCount = 0;

void Count(int n, int x, int y, vector<vector<int>> &board) {
    int tmpMinus = 0;
    int tmpZero = 0;
    int tmpPlus = 0;

    for (int i = x; i < x + n; i++) {
        for (int j = y; j < y + n; j++) {
            if (board[i][j] == -1)
                tmpMinus++;
            else if (board[i][j] == 0)
                tmpZero++;
            else
                tmpPlus++;
        }
    }

    if (tmpMinus == n * n)
        minusCount++;
    else if (tmpZero == n * n)
        zeroCount++;
    else if (tmpPlus == n * n)
        plusCount++;
    else {
        // 색종이가 하나의 색으로 구성된 경우가 아니므로 분할하기
        // 9 개로 분할해야함
        int third = n / 3;

        Count(third, x, y, board);
        Count(third, x, y + third, board);
        Count(third, x + third, y, board);
        Count(third, x + third, y + third, board);
        Count(third, x, y + 2 * third, board);
        Count(third, x + 2 * third, y, board);
        Count(third, x + 2 * third, y + 2 * third, board);
        Count(third, x + third, y + 2 * third, board);
        Count(third, x + 2 * third, y + third, board);
    }
    return;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    vector<vector<int>> board(n);
    for (int i = 0; i < n; i++) {
        board[i] = vector<int>(n);

        for (int j = 0; j < n; j++) {
            cin >> board[i][j];
        }
    }
    Count(n, 0, 0, board);
    cout << minusCount << "\n" << zeroCount << "\n" << plusCount;


    return 0;
}

 

2630 번 색종이 만들기 문제랑 다를 바가 없는 문제였다.

 

Count 메서드에 진입하면 -1, 0, 1의 개수를 세는데 만약 현 단계의 색종이가 하나의 번호로만 되어 있으면 해당 종이의 수를 +1 해주면 된다.

 

만약 다른 색으로 이루어져 있다면 현 단계의 종이를 9개로 분할해준 다음 똑같은 과정을 반복하면 된다.

 

처음으로 제출했던 코드가 1% 에서 안 올라가고 시간초과가 떴는데 Count 에서 벡터를 넘겨줄 때 & 를 사용하지 않았기 때문이다. & 를 사용하지 않으면 메서드에 진입할 때마다 board 값을 복사하는데 이게 시간이 오래걸려서 시간초과가 나는 것이었다.

 

즉, 메서드에 진입할 때마다 board 의 값을 복사하는 것을 막기 위해 & 을 사용해주면 된다.

 

 

참고자료:

글 읽기 - 1780번 데이터 타입이 시간에 영향을 끼칠까요?

-> 답변 덕분에 시간 초과 원인을 찾을 수 있었다.

 

[바킹독의 실전 알고리즘] 0x0B강 - 재귀 - YouTube