반응형
🔺 문제
🧩 해결 아이디어
• 브루트포스, 2차원 누적합
1. dp 배열을 채운다.
dp 배열의 왼쪽 값 + dp 배열의 위쪽 값 - 2번 받아 중복되는 dp 배열의 왼쪽 위 대각선 값 + map 배열의 현재 위치 값
2. dp 배열을 돌며 최댓값을 구한다.
💥 유의사항
최댓값 비교 할 때, long형으로 받고 비교해야 한다.
🔺 코드
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
|
import java.util.*;
import java.io.*;
public class Main {
static int N, M;
static int[][] map, dp;
static long max = Integer.MIN_VALUE; // long !!
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N + 1][M + 1];
dp = new int[N + 1][M + 1];
for(int i = 1 ; i <= N ; i++) {
st = new StringTokenizer(br.readLine(), " ");
for(int j = 1 ; j <= M ; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
for(int i = 1 ; i <= N ; i++) {
for(int j = 1 ; j <= M ; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + map[i][j];
}
}
for(int x1 = 1 ; x1 <= N ; x1++) {
for(int y1 = 1 ; y1 <= M ; y1++) {
for(int x2 = x1 ; x2 <= N ; x2++) {
for(int y2 = y1 ; y2 <= M ; y2++) {
long result = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
max = Math.max(max, result);
}
}
}
}
System.out.println(max);
}
}
|
cs |
💬 느낀 점
2차원 누적합에 익숙해집시다....
예~~~전에 풀었던.. 잊고 있던 백준 구간 합 구하기 5 문제가 생각났다.
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
12.1 |
(참고)
✔ 풀이 참고
✔ 그림 복습용 (구하는 영역)
반응형
'코테 > 백준' 카테고리의 다른 글
[백준/JAVA] 20002번: 사과나무 (1) | 2023.12.08 |
---|---|
[백준/JAVA] 2346번: 풍선 터뜨리기 (0) | 2023.12.07 |
[백준/JAVA] 4920번: 테트리스 게임 (0) | 2023.12.01 |
[백준/JAVA] 1251번: 단어 나누기 (0) | 2023.11.30 |
[백준/JAVA] 18114번: 블랙 프라이데이 (0) | 2023.11.30 |