ALGORITHM/BOJ
[백준] 2630 색종이 만들기
0298
2021. 7. 9. 16:41
https://www.acmicpc.net/problem/2630
2630번: 색종이 만들기
첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다.
www.acmicpc.net
2021-07-09
|
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
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main2630 {
public static int N, white, blue;
public static int[][] arr;
public static void solve(int size, int x, int y) {
if(size == 1) {
if(arr[x][y] == 0) white++;
else blue++;
return;
}
if(check(size, x, y, arr[x][y])) {
return;
}
solve(size/2, x, y);
solve(size/2, x, y+size/2);
solve(size/2, x+size/2, y);
solve(size/2, x+size/2, y+size/2);
}
public static boolean check(int size, int x, int y, int color) {
for(int i = x; i < x+size; i++) {
for(int j = y; j < y+size; j++) {
if(arr[i][j] != color) return false;
}
}
if(color == 0) white++;
else blue++;
return true;
}
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
N = Integer.parseInt(st.nextToken().trim());
white = 0;
blue = 0;
arr = new int[N][N];
for(int i = 0; i < N; i++) {
st = new StringTokenizer(bf.readLine());
for(int j = 0; j < N; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
solve(N, 0, 0);
System.out.println(white);
System.out.println(blue);
}
}
|
cs |
#문제풀이
분할정복
색종이를 계속 4등분한다고 생각하면 된다.