백준 1780 종이의 개수

작성일 | In |

Problem : 종이의 개수

유형 : 분할 정복

문제 해석

  • 각 종류별 종이의 개수를 구하라.

문제 재해석

  • 범위내 수가 모두 같을 경우에만, 종이를 자를 수 있다.
  • 그렇지 않은 경우는 9개로 자른다.

해결 전략

  • 종이가 최소 크기로 잘릴수 있는 경우는 숫자가 단 한개가 있는 경우이다.
  • 큰 경우부터 잘라가며 분할 정복한다.

구현, 설계

  • 3 ^ 7 이 최대 크기이므로, 조금 더 크게 배열의 크기를 잡느다.
  • 모두 같은 숫자인지 확인한다.
  • 모두 같은 숫자가 되는 최소의 경우는 한개의 숫자만 있는 경우이다.
  • 모두 같은 숫자가 아니라면 9면으로 자르고 재귀적으로 처음단계로 돌아간다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;

int n, answer[3];
int board[2200][2200]; // 3 ^ 7 = 2189

void PaperCountUp(int x, int y) {
    int paperKind = board[x][y];
    answer[paperKind + 1]++;
}

bool IsAllSame(int x, int y, int len) {
    int base = board[x][y];
    for (int i = x; i < x + len; ++i) {
        for (int ii = y; ii < y + len; ++ii) {
            if (board[i][ii] == base) continue;
            return false;
        }
    }
    return true;
}

void PaperCheck(int x, int y, int len) {
    if (IsAllSame(x, y, len)) {
        PaperCountUp(x, y);
        return;
    }

    int AThird = len / 3;
    for (int i = 0; i < 3; ++i) {
        for (int ii = 0; ii < 3; ++ii) {
			PaperCheck(x + i * AThird, y + ii * AThird, AThird);
		}
    }
}

void Solve() {
    PaperCheck(0, 0, n);
    for (const int &paperKind : answer) {
        cout << paperKind << "\n";
    }
}

void Input() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < n; ++ii) {
            cin >> board[i][ii];
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);
    Input();
    Solve();

    return 0;
}

피드백

  • 분할 정복 문제푸는 속도가 점점 빨라지기 시작했다.
  • 빨라지는것이 아닌, 자신있을때까지 연습하자.