728x90
반응형
https://www.acmicpc.net/problem/1780
1780번: 종이의 개수
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수
www.acmicpc.net
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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int n;
public static int m;
public static int[][] arr;
public static int[] totalNum = new int[3];
public static boolean check(int row, int col, int n) {
int standard = arr[row][col];
for (int i = row; i < row + n; i++) {
for (int j = col; j < col + n; j++) {
if (standard != arr[i][j]) {
return false;
}
}
}
return true;
}
public static void divide(int row, int col, int n) {
if (check(row, col, n)) {
totalNum[arr[row][col] + 1]++;
} else {
// 분할
int num = n / 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
divide(row + (i * num), col + (j * num), num);
}
}
}
}
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
arr = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= n; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
divide(1, 1, n);
for (int i = 0; i < 3; i++) {
System.out.println(totalNum[i]);
}
}
}
|
cs |
분할정복을 이용해서 풀면 된다.
메서드가 두가지 필요한데, 한 가지는 배열을 쪼개주는 메서드 하나는 배열의 모든 원소가 같은 원소인지 판단해주는 메서드이다.
divide가 배열을 쪼개주는 메서드인데
if (check(row, col, n)) {
totalNum[arr[row][col] + 1]++;
}
--> 만약 모두 같은수라면 상관이 없지만
else {
// 분할
int num = n / 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
divide(row + (i * num), col + (j * num), num);
}
}
}
--> 하나라도 다른 수가 있다면 종이를 쪼개줘야한다.
이때 3으로 나누는건 어차피 n이 3의 제곱수이기 때문에 분할을 할때 항상 3으로 나누게 된다.
참고한 사이트
https://developer-mac.tistory.com/38
[Java]백준 1780번 :: 종이의 개수
백준 온라인 저지 1780번 '종이의 개수' Java 알고리즘 문제풀이 풀이 이 문제는 분할정복(Divide and Conquer)로 풀면된다. 분할정복은 정말 쉬운 개념이다. (유사한 분할정복 문제 풀기 -> 백준 1992번 쿼
developer-mac.tistory.com
728x90
반응형
'알고리즘 > 분할정복' 카테고리의 다른 글
[java 백준] plat 5/ 1517번 버블정렬 (0) | 2022.02.05 |
---|---|
[java 백준]골드 4/2448번 별 찍기 -11 (0) | 2022.02.03 |
[java 백준] 실버 1/별찍기 -10 (0) | 2022.01.30 |
[java 백준]실버 1/ 1992번 쿼드트리 (0) | 2022.01.30 |
[java 백준] 실버 5/11728번 배열 합치기 (0) | 2022.01.28 |
댓글