[백준] 20002: 사과나무 - JAVA

15 Jul 2023 in Algorithm on 브루트포스 알고리즘

https://www.acmicpc.net/problem/20002

풀이

2차원 누적합을 만들어 값을 찾는 문제였다.

한 변의 길이가 N인 2차원 누적합 배열을 만드려면 N + 1사이즈의 이차원 배열을 만들고 1부터 값을 채운다.

int[][] prefix_sum = new int[N + 1][N + 1];
for (int i = 1; i < N + 1; i++) {
    int num = Integer.parseInt(br.readLine());
    for (int j = 1; j < N + 1; j++) {
        board[i][j] = board[i - 1][j] + board[i][j - 1] + num - board[i - 1][j - 1];
    }
}

값을 찾으려면 이와 반대로 빼고 더해준다.

---

메모리: 23072KB

시간: 376ms

언어: Java 11

코드

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));
        int N = Integer.parseInt(br.readLine());
        int[][] board = new int[N + 1][N + 1];
        StringTokenizer st;
        for (int i = 1; i < N + 1; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j < N + 1; j++) {
                board[i][j] = board[i - 1][j] + board[i][j - 1] + Integer.parseInt(st.nextToken())
                        - board[i - 1][j - 1];
            }
        }

        int ans = board[1][1];
        int size = 0;
        while (size++ < N) {
            for (int i = size; i < N + 1; i++) {
                for (int j = size; j < N + 1; j++) {
                    int sum = board[i][j] - board[i - size][j] - board[i][j - size] + board[i - size][j - size];
                    ans = Math.max(sum, ans);
                }
            }
        }

        System.out.println(ans);
    }

}