boj)1780 - 종이의 개수
2020. 11. 13. 14:57ㆍPS/boj
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
|
import java.io.*;
import java.util.*;
public class boj_1780 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int N;
static int[] cnt;
static int[][] map;
public static void main(String[] args) throws IOException {
input();
divideAndConquer(0, 0, N);
for (int value : cnt) {
System.out.println(value);
}
}
static void input() throws IOException {
N = Integer.parseInt(br.readLine());
map = new int[N][N];
cnt = new int[3]; // 0, 1, 2
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken()) + 1;
}
}
}
static boolean isSame(int x, int y, int length) {
int val = map[x][y];
for (int i = x; i < x + length; i++) {
for (int j = y; j < y + length; j++) {
if (val != map[i][j]) return false;
}
}
return true;
}
static void divideAndConquer(int x, int y, int length) {
if (isSame(x, y, length)) {
cnt[map[x][y]]++;
} else {
int newLength = length / 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
divideAndConquer(x + newLength * i,y + newLength * j, newLength);
}
}
}
}
}
|
cs |
- 분할정복 / 재귀
- 실버2 인데 왜 이렇게 어려운거 같지,, 아이디어는 떠오르는데 그대로 만들기가 어렵다.
- 재귀랑 분할정복 여러개 풀어 봐야겠다.
'PS > boj' 카테고리의 다른 글
boj)16505 - 별 (0) | 2020.11.14 |
---|---|
boj)1992 - 쿼드트리 (0) | 2020.11.13 |
boj)17478 - 재귀함수가 뭔가요? (0) | 2020.11.12 |
boj)1074 - Z (0) | 2020.11.12 |
boj)11729 - 하노이 탑 이동 순서 (0) | 2020.11.11 |