문제링크
위처럼 입력이 주어졌을 때 아래처럼 변의 길이를 N/2씩 나누어 가며 흰색으로 만들어진 정사각형과 파란색으로 만들어진 정사각형의 개수를 출력해야한다.
문제를 보면 잘 알겠지만 대놓고 분할정복의 방법을 사용하라고 그림까지 주어져있다. 분할정복의 자세한 내용은 알고리즘 카테고리에서 다루도록하고 간단하게 설명하면 하나의 문제를 같지만 더 작은 문제로 나눈다음 작은 문제를 해결하고 결과를 합쳐서 하나의 결과가 나오도록하게 하는 전략이다.
분할정복을 문제에 적용해보면 한 변의 길이가 N/2인 정사각형이 흰색 또는 파란색의 정사각형을 만들지 못할 경우 변의 길이를 N/2로 나누어 다시 확인한다.(분할)
만약 한 변의 길이가 N/2인 정사각형이 전부 흰색 또는 전부 파란색으로 이루어져있다면 흰색종이의 개수, 파란색 종이의 개수를 더해주고 해당 스텝을 종료한다.(정복)
더 자세한 설명은 코드와 주석으로 설명하겠다. (혹시 의문이 있으시면 댓글 달아주세요!)
코드
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
75
76
77
78
79
80
81
82
83
84
|
#include <iostream>
using namespace std;
int n, white, blue;
bool board[129][129];
// x좌표, y좌표, 변의 길이 를 인자로 받음
void rec(int r, int c, int n) {
if (n == 1) {
if (board[r][c] == 1) {
blue++;
}
else if (board[r][c] == 0) {
white++;
}
return;
}
bool w = true; // 모두 흰색인지 체크하는 flag
bool b = true; // 모두 파란색인지 체크하는 flag
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// 하나라도 흰색이 아니면 탐색 stop -> 흰색종이 X
if (board[r + i][c + j] != 0) {
w = false;
break;
}
}
if (w == false) {
break;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// 하나라도 파란색이 아니면 탐색 stop -> 파란종이 X
if (board[r + i][c + j] != 1) {
b = false;
break;
}
}
if (b == false) {
break;
}
}
// b == true 이면 탐색한 면 모두 파란색임
if (b == true) {
blue++;
return;
}
// w == true 이면 탐색한 면 모두 파란색임
else if (w == true) {
white++;
return;
}
// 아니라면 4분할 하여 재탐색
else {
rec(r, c, n / 2); // 1사분면
rec(r + n / 2, c, n/2); // 3사분면
rec(r, c + n / 2, n/2); // 2사분면
rec(r + n / 2, c + n / 2, n/2); // 4사분면
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> board[i][j];
}
}
rec(1, 1, n);
cout << white << '\n';
cout << blue << '\n';
return 0;
}
|
cs |
메모
해당 문제를 보면 정답률이 거의 70%나 되는 문제지만 분할 정복이 익숙하지 않은 나에게는 어려웠던 문제다. 문제해결기법을 수강하다 분할정복의 개념과 이해가 부족한 것 같아 찾아 풀었던 문제다. 분할정복 카테고리의 문제를 조금 더 풀어보고, 더 좋은 코드 짜는 법을 공부해야겠다.
+추가 수정코드 -> 더 깔끔한 풀이(?)
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
|
#include <iostream>
using namespace std;
int n, white, blue;
bool board[129][129];
void rec(int r, int c, int n) {
int cnt = 0; // 색칠된 개수 저장
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (board[r + i][c + j] == 1) {
cnt++;
}
}
}
// 0개면 모두 흰색
if (cnt == 0) {
white++;
return;
}
// n*n개면 모두 파란색
else if (cnt == n * n) {
blue++;
return;
}
// 분할정복
else {
rec(r, c, n / 2);
rec(r + n / 2, c, n / 2);
rec(r, c + n / 2, n / 2);
rec(r + n / 2, c + n / 2, n / 2);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> board[i][j];
}
}
rec(1, 1, n);
cout << white << '\n';
cout << blue << '\n';
return 0;
}
|
cs |