[Gold V] 사과나무 - 20002 (JAVA)

문제 요약

N × N 크기의 정사각형 모양 과수원이 있고, N × N 개의 사과나무가 1 × 1 크기의 간격으로 모든 칸에 심어져있다.

농부 형곤이가 가을을 맞아 사과를 수확하려는데, 땅주인 신영이가 "너는 과수원 내에 사과나무를 K × K 의 크기의 정사각형 모양으로만 수확해 가져갈 수 있어, 이때 K는 1보다 크거나 같고 N보다 작거나 같은 정수라구! 나머지는 내가 먹을께! 하하!" 라고 통보했다.

하나의 사과나무를 수확할 때, 사과를 통해 얻을 수 있는 이익과 노동비로 빠져나가는 손해가 동시에 이루어진다.

그래서 형곤이는 나무의 위치를 좌표로 하여, 사과를 통해 얻은 이익과 노동비를 더한 총이익을 2차원 배열의 형태로 정리했다.

악독한 땅주인 신영이로부터 고통받는 귀여운 형곤이에게 최대 총이익을 안겨주고 싶은 당신, 형곤이를 도와주자!

---

문제 분석

최근 현토버 코테를 보고 누적합 알고리즘을 한번 공부했었기에, 바로 누적합 문제인 것을 알았다.

본 배열을 저장하고, 누적합 배열을 하나 만든 후 k사이즈별 기준에 맞게 합을 계산하며 최댓값을 찾아준다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];

        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int idx = 0;
            while (st.hasMoreTokens()) {
                map[i][idx++] = Integer.parseInt(st.nextToken());
            }
        }
        // 점화식을 통해 계산하기 위해 크기를 N+1로 지정해준다.
        int[][] sumMap = new int[N + 1][N + 1];

        for (int r = 1; r <= N; r++) {
            for (int c = 1; c <= N; c++) {
                sumMap[r][c] = map[r - 1][c - 1] + sumMap[r - 1][c] + sumMap[r][c - 1] - sumMap[r - 1][c - 1];
            }
        }
        int max = -10000;
        // K는 1보다 크거나 같고 N보다 작거나 같은 정수라구!
        // 그리고 sumMap의 사이즈는 N+1이기에 r과 c를 N까지 반복해준다.
        // 또한 k = 1이기 때문에 실질적으로 원본 배열의 0,0부터 탐색하는것이다.
        for(int k = 1; k <= N; k++){
            for(int r = k; r <= N; r++){
                for(int c = k; c <= N; c++){
                    int sum = sumMap[r][c] - sumMap[r - k][c] - sumMap[r][c - k] + sumMap[r - k][c - k];
                    max = Math.max(sum, max);
                }
            }
        }
        System.out.println(max);
    }
}

---

정리

새로 배운 내용

이차원 배열에서 누적합을 사용하는 문제를 처음 풀어봤다. 

개선할 점

솔직히 최대값 찾는 과정에서 반복문의 인자들이 저 조건이 맞는지 확실하지 않았던 상태에서 운 좋게 맞은 경우다. 잠 좀 깨면 다시 한번 확인하면서 답습해야 할 필요가 있다.

더 찾아볼만한 사항

관련된 다른 문제들을 풀어보자.

 

---