1780번: 종이의 개수
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다.
www.acmicpc.net
<풀이>
1. 정사각형 종이의 한 변 크기인 N과 종이의 모양을 입력받는다.
2. 해당 종이를 지정한 방식으로 잘랐을 때, 각 종류별 종이의 개수를 출력한다.
<해법>
1. 자르는 방식을 분석하는 방법
=> 주어진 종이를 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
63
64
65
66
67
68
69
70
71
72
73
74
|
#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;
}
|
분할 정복에 대해 알아볼 수 있는 문제였습니다.
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
| [C++] 백준 2156 - 포도주 시식 (0) | 2021.01.25 |
|---|---|
| [C++] 백준 1074 - Z (0) | 2021.01.18 |
| [C++] 백준 2447 - 별 찍기 10 (0) | 2021.01.14 |
| [C++] 백준 12100 - 2048(Easy) (0) | 2021.01.10 |
| [C++] 백준 1018 - 체스판 다시 칠하기 (0) | 2021.01.06 |
