[백준] 20002 사과나무 - Java

 

 

 

문제 출저

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

20002번: 사과나무

 

 

 

문제 풀이

한 변의 크기가 n인 2차원 배열이 주어집니다. 이 때 k 크기로 정사각형을 자릅니다. k는 n 이하의 수 입니다. 이 때, k 크기로 자른 정사각형의 합이 가장 클 때를 구해야 합니다. 

 

누적합으로 풀었습니다. 

int[][] prefix로 누적합 배열을 만들고 1부터 n까지의 숫자를 입력값으로 k로 받아 k 정사각형들을 탐색하는 메소드를 만들어 문제를 풀었습니다.

 

 

 

소스 코드

package baekjoon.backjoon11.day0110.day02;


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

/*
사과나무
https://www.acmicpc.net/problem/20002
 */
public class B20002 {

  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][n];



    for(int i = 0; i < n; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      for(int j = 0; j < n; j++) {
        board[i][j] = Integer.parseInt(st.nextToken());
      }
    }

    int[][] prefix = new int[n+1][n+1];

    for(int i = 1; i < n+1; i++) {
      for(int j = 1; j < n+1; j++) {
        prefix[i][j] = board[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1];
      }
    }

    int answer = -1000;

    for(int k = 1; k < n+1; k++) {
      int number = search(k, prefix);
      answer = Math.max(answer, number);
    }

    System.out.println(answer);

  }

  public static int search(int k, int[][] prefix) {
    int result = -1000;
    int n = prefix.length;

    for(int i = k; i < n; i++) {
      for(int j = k; j < n; j++) {
        int number = prefix[i][j] - prefix[i-k][j] - prefix[i][j-k] + prefix[i-k][j-k];
        result = Math.max(result, number);
      }
    }

    return result;

  }

}