풀이 방법
배열의 누적합을 이용해서 나타내고 가능한 모든 분을 비교하며 풀어주었다.
내 코드
package com.company;
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
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());
long max = Long.MIN_VALUE;
long[][] array = new long[N + 1][M + 1];
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= M; j++) {
long x = Long.parseLong(st.nextToken());
array[i][j] = array[i - 1][j] + array[i][j - 1] - array[i - 1][j - 1] + x;
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
for (int u = i; u <= N; u++) {
for (int v = j; v <= M; v++) {
max = Math.max(max, array[u][v] + array[i - 1][j - 1] - array[u][j - 1] - array[i - 1][v]);
}
}
}
}
System.out.println(max);
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
뱀과 사디리 게임 - 16928번 (0) | 2021.10.27 |
---|---|
택배 - 1719번 (0) | 2021.10.26 |
색종이와 가위 - 20444번 (0) | 2021.10.25 |
네트워트 연결 - 1922번 (0) | 2021.10.22 |
오리 - 12933번 (0) | 2021.10.22 |