📙[Algo] 24.05.11 알고리즘

알고리즘 문제) BOJ 20002. 사과나무

• 링크 : https://www.acmicpc.net/problem/20002

문제 요약

• N*N크기 배열이 주어짐
• 해당 배열에는 각 칸마다 사과나무가 심어져있고, 사과 수확을 통해 얻은 이익과 노동비를 더한 총이익을 표시함
• K*K크기 정사각형 모양으로만 딱 한 번 수확할 수 있으며, 이때 얻을 수 있는 최대 총이익은?

시간 제한

• 1초

입력

• 과수원 크기 N
  • 1 ≤ N ≤ 300
• 두번째 줄~N+1번째 줄까지 해당 나무 수확했을때 얻을 총 이익 표시
  • -1000~1000

출력

• 이익 최댓값 출력

접근법

• 2차원 배열 누적합 연습하고싶어서 푼 문제
• 2차원 누적합 배열 만들고(이익 누적합 저장), K*K칸만큼 탐색하면서 이익을 최댓값으로 갱신(for문으로 k를 1~N까지 돔)

코드

//
import java.io.*;
import java.util.*;


public class Main {
    static int N;
    static int[][] arr = new int[310][310];
    static int[][] acc = new int[310][310];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        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());
            }
        }

        // 2차원 누적합 배열 만들기
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                acc[i][j] = acc[i][j - 1] + acc[i - 1][j] - acc[i - 1][j - 1] + arr[i][j];
            }
        }

        // K=1 ~ N 하나하나 탐색하면 최댯값 갱신
        int answer = Integer.MIN_VALUE, sum;
        for (int k = 1; k <= N; k++) {
            for (int i = k; i <= N; i++) {
                for (int j = k; j <= N; j++) {
                    sum = acc[i][j] - acc[i][j - k] - acc[i - k][j] + acc[i - k][j - k];

                    answer = Math.max(answer, sum);
                }
            }
        }

        System.out.println(answer);

        br.close();
    }
}