[백준] 1780번 : 종이의 개수

문제

 

---

풀이

 

myunji.tistory.com/251

[백준] 2630번 : 색종이 만들기

이 문제에서 거의 한줄만 수정하면 된다.

 

4번 쪼개던걸 9번 쪼개니까 4(2*2)번 돌던 for문을 9(3*3)번 돌게 하면 되는 것이다.

---

소스코드

 

#include <iostream>

using namespace std;

int paper[2187][2187];
int nums[3]; //nums[0] = -1, nums[1] = 0, nums[2] = 1

bool isSame(int size, int row, int col, int num) {
    for (int i = row; i < (size + row); i++) {
        for (int j = col; j < (size + col); j++) {
            if (paper[i][j] != num)
                return false;
        }
    }
    return true;
}

void divide(int size, int row, int col) {
    int num = paper[row][col];

    if (isSame(size, row, col, num)) { //종이의 색이 모두 같음
        nums[num + 1]++;
    } else { //분할
        int resize = size / 3;
        for (int i = 0; i <= (resize * 2); i += resize)
            for (int j = 0; j <= (resize * 2); j += resize)
                divide(resize, row + i, col + j);
    }
}

int main() {
    int N;

    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            cin >> paper[i][j];
    }
    divide(N, 0, 0);
    cout << nums[0] << '\n' << nums[1] << '\n' << nums[2] << '\n';
}

전체 소스코드다.

 

int paper[2187][2187];
int nums[3]; //nums[0] = -1, nums[1] = 0, nums[2] = 1

최대 입력크기에 맞춰서 paper 배열의 크기를 늘려주고, 들어오는 데이터의 종류가 3개가 됐으니 nums 배열도 하나 늘려준다.

 

void divide(int size, int row, int col) {
    int num = paper[row][col];

    if (isSame(size, row, col, num)) { //종이의 색이 모두 같음
        nums[num + 1]++;
    } else { //분할
        int resize = size / 3;
        for (int i = 0; i <= (resize * 2); i += resize)
            for (int j = 0; j <= (resize * 2); j += resize)
                divide(resize, row + i, col + j);
    }
}

9개로 쪼개야 하니까 size를 3으로 나누고 for문을 각 3번씩 총 9번 돌도록 수정한다.