반응형
문제링크 : https://www.acmicpc.net/problem/1451
1451번: 직사각형으로 나누기
첫째 줄에 직사각형의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 직사각형에 들어가는 수가 가장 윗 줄부터 한 줄에 하나씩 M개의 수가 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 직사각형엔 적어도 3개의 수가 있다. 또, 직사각형에 들어가는 수는 한 자리의 숫자이다.
www.acmicpc.net
내가 가장 싫어하는 전형적인 그리디 문제이다-_- 아... 이런 문제 진짜 싫다. 하나라도 빠뜨리면 안되는... 실수할 여지도 너무 많고...ㅠㅠ 아무튼 문제에 대한 설명을 해보겠다. 직사각형을 작은 3개의 직사각형으로 나눌 수 있는 경우의 수는 아래 그림과 같이 총 6가지이다.
이렇게 총 6가지 경우에 대해 모두 계산을 해서 이 중에 가장 큰 값을 구하면 된다... 코드는 아래와 같다.
|
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[][] rectangle = new int[n][m];
for(int i = 0; i < n; i++) {
char[] temp = br.readLine().toCharArray();
for(int j = 0; j < m; j++) {
rectangle[i][j] = temp[j] - '0';
}
}
long max = 0;
for(int i = 1; i < n; i++) {
long a = getRectangleSum(0, i, 0, m, rectangle);
for(int j = 1; j < m; j++) {
long b = getRectangleSum(i, n, 0, j, rectangle);
long c = getRectangleSum(i, n, j, m, rectangle);
long tmp = a * b * c;
if(max < tmp) {
max = tmp;
}
}
for(int j = i + 1; j < n; j++) {
long b = getRectangleSum(i, j, 0, m, rectangle);
long c = getRectangleSum(j, n, 0, m, rectangle);
long tmp = a * b * c;
if(max < tmp) {
max = tmp;
}
}
}
for(int i = n - 1; i > 0; i--) {
long a = getRectangleSum(i, n, 0, m, rectangle);
for(int j = 1; j < m; j++) {
long b = getRectangleSum(0, i, 0, j, rectangle);
long c = getRectangleSum(0, i, j, m, rectangle);
long tmp = a * b * c;
if(max < tmp) {
max = tmp;
}
}
}
for(int i = 1; i < m; i++) {
long a = getRectangleSum(0, n, 0, i, rectangle);
for(int j = 1; j < n; j++) {
long b = getRectangleSum(0, j, i, m, rectangle);
long c = getRectangleSum(j, n, i, m, rectangle);
long tmp = a * b * c;
if(max < tmp) {
max = tmp;
}
}
for(int j = i + 1; j < m; j++) {
long b = getRectangleSum(0, n, i, j, rectangle);
long c = getRectangleSum(0, n, j, m, rectangle);
long tmp = a * b * c;
if(max < tmp) {
max = tmp;
}
}
}
for(int i = m - 1; i > 0; i--) {
long a = getRectangleSum(0, n, i, m, rectangle);
for(int j = 1; j < n; j++) {
long b = getRectangleSum(0, j, 0, i, rectangle);
long c = getRectangleSum(j, n, 0, i, rectangle);
long tmp = a * b * c;
if(max < tmp) {
max = tmp;
}
}
}
System.out.println(max);
}
private static long getRectangleSum(int sI, int eI, int sJ, int eJ, int[][] rectangle) {
long sum = 0;
for(int i = sI; i < eI; i++) {
for(int j = sJ; j < eJ; j++) {
sum += rectangle[i][j];
}
}
return sum;
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
뭔가 메서드로 빼고 싶은 욕구가 용솟음친다... 근데 딱히 뺄 게 없어 보였다. 그나마 메서드로 뺀 코드는 아래와 같다.
|
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
85
86
87
88
89
90
91
92
93
94
95
96
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[][] rectangle = new int[n][m];
for(int i = 0; i < n; i++) {
char[] temp = br.readLine().toCharArray();
for(int j = 0; j < m; j++) {
rectangle[i][j] = temp[j] - '0';
}
}
long max = 0;
for(int i = 1; i < n; i++) {
long a = getRectangleSum(0, i, 0, m, rectangle);
max = getMaxVertical(a, rectangle, max, i, n, 0, m);
max = getMaxHorizontal(a, rectangle, max, i, n, 0, m);
}
for(int i = n - 1; i > 0; i--) {
long a = getRectangleSum(i, n, 0, m, rectangle);
max = getMaxVertical(a, rectangle, max, 0, i, 0, m);
}
for(int i = 1; i < m; i++) {
long a = getRectangleSum(0, n, 0, i, rectangle);
max = getMaxHorizontal(a, rectangle, max, 0, n, i, m);
max = getMaxVertical(a, rectangle, max, 0, n, i, m);
}
for(int i = m - 1; i > 0; i--) {
long a = getRectangleSum(0, n, i, m, rectangle);
max = getMaxHorizontal(a, rectangle, max, 0, n, 0, i);
}
System.out.println(max);
}
private static long getMaxHorizontal(long a, int[][] rectangle, long max, int sI, int eI, int sJ, int eJ) {
for(int j = sI + 1; j < eI; j++) {
long b = getRectangleSum(sI, j, sJ, eJ, rectangle);
long c = getRectangleSum(j, eI, sJ, eJ, rectangle);
long tmp = a * b * c;
if(max < tmp) {
max = tmp;
}
}
return max;
}
private static long getMaxVertical(long a, int[][] rectangle, long max, int sI, int eI, int sJ, int eJ) {
for(int j = sJ + 1; j < eJ; j++) {
long b = getRectangleSum(sI, eI, sJ, j, rectangle);
long c = getRectangleSum(sI, eI, j, eJ, rectangle);
long tmp = a * b * c;
if(max < tmp) {
max = tmp;
}
}
return max;
}
private static long getRectangleSum(int sI, int eI, int sJ, int eJ, int[][] rectangle) {
long sum = 0;
for(int i = sI; i < eI; i++) {
for(int j = sJ; j < eJ; j++) {
sum += rectangle[i][j];
}
}
return sum;
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
메서드로 빼도 딱히 많은 이점이 있는 것 같지는 않다. 이런 문제는 극혐이나 알고리즘 테스트에 나온다면 풀어야하니 어쩔 수 없이 연습을 해야겠지...ㅠㅠ
반응형
'알고리즘' 카테고리의 다른 글
| 백준(BOJ) 2186 : 문자판 (JAVA) (0) | 2020.02.11 |
|---|---|
| 백준(BOJ) 11053 : 가장 긴 증가하는 부분 수열 (JAVA) (0) | 2020.02.11 |
| 백준(BOJ) 7453 : 합이 0인 네 정수 (JAVA) (0) | 2020.02.10 |
| 백준(BOJ) 1912 : 연속합 (JAVA) (0) | 2020.02.07 |
| 백준(BOJ) 11662 : 민호와 강호 (JAVA) (0) | 2020.02.07 |