[Boj_20002] 사과나무

📎 문제 링크

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

20002번: 사과나무

 

▸ 문제

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

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

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

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

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

 

▸ 입력

첫 번째 줄에는 과수원의 크기 N이 주어진다. (1 ≤ N ≤ 300)

두 번째 줄부터 N + 1번째 줄까지, 해당 나무를 수확했을 때 얻을 수 있는 총이익을 표시한다.

총이익은 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

 

▸ 출력

첫 번째 줄에 최댓값을 출력한다.

 

📍 문제 정보

• 🥇 문제 레벨 : 골드 5
• 🔔  문제 유형 : 브루트포스 알고리즘, 누적 합
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

• 입력으로 주어진 해당 나무를 수확했을 때 얻을 수 있는 총이익에 대한 누적합을 저장할 배열을 생성한 뒤, 배열에 누적합을 계산하여 저장했다.
• k의 크기가 정해져 있지 않기 때문에 k가 1부터 n일 때까지 모든 경우의 수를 탐색하며, 모든 경우의 수에서 나올 수 있는 총이익의 최댓값을 갱신해 주었다.

 

✔ 최종 코드

메모리 : 21472KB
시간 : 328ms

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static int n;
    static int[][] map;
    static int[][] prefix;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine()); // nxn 과수원의 크기
        map = new int[n+1][n+1]; // 총이익을 저장할 배열
        prefix = new int[n+1][n+1]; // 총이익의 누적합을 저장할 배열
        StringTokenizer st;
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                // 2차원 배열의 누적합 구하기 (총이익의 누적합)
                prefix[i][j] = map[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1];
            }
        }

        int ans = Integer.MIN_VALUE; // 모든 kxk 크기에서 나올 수 있는 총이익의 최댓값
        for (int i = 1; i <= n; i++) {
            int tmp = check(i); // 1부터 n까지 각 kxk 크기에 대한 총이익 구하기
            ans = Math.max(ans, tmp); // 최댓값 갱신
        }
        bw.append(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    private static int check(int k) {
        int max = Integer.MIN_VALUE; // kxk 크기의 총이익의 최댓값
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i+k-1 > n || j+k-1 > n) continue; // 범위 벗어나면 건너띄기
                // kxk 크기의 총이익
                int tmp = prefix[i+k-1][j+k-1] - prefix[i-1][j+k-1] - prefix[i+k-1][j-1] + prefix[i-1][j-1];
                max = Math.max(max, tmp); // 최댓값 갱신
            }
        }
        return max;
    }
}

 

 

📍 함께 풀어보면 좋은 백준 문제

• 2차원 배열의 합
• 체스판 다시 칠하기 2