[JAVA|UVa] 108 Maximum Sum

자바 연습이 좀 필요해서, UVa 문제를 좀 풀어보려 한다. 처음 문제를 풀었다.

문제를 제출할 때 main 메소드가 들어있는 클래스의 이름은 Main 이어야 하는 것 같다. 이것 때문에 여러 차례 빠꾸 맞음.

우선 코드.

import java.util.Scanner;

public class Main {

   private static int N;
   private static int[][] a = null;
   private static int x_s , x_e;
   
   public static void main(String arg[]) {

       getData1();
       
       System.out.println(findMaxSum1());
   }
   
   private static void getData1() {
       Scanner scnr = new Scanner(System.in);
       N = scnr.nextInt();
       a = new int[N][N];
       for(int i = 0; i<N*N; i++) {
           a[i/N][i%N] = scnr.nextInt();
       }
   }
   
   private static int findMaxSum1() {
       int sum;
       int sum_x = 0;
       
       for(x_s = 0; x_s < N; x_s++) {
           for(x_e = x_s; x_e < N; x_e++) {
               // x_s와 x_e 를 고정하고 나면
               //

               // 아래 부분은 일차원의 최대 부분합을 구하는 것과 동일하다.
               // 1차원 수열의 연속된 부부의 최대 합은 처음부터의 합만을
               // 지켜보다가 합이 음수로 떨어지면, 그 때를 기준점으로 삼으면
               // 된다.

               sum = 0;
               for(int y = 0; y < N; y++) {
                   sum += hline_sum(y);
                   if(sum < 0) {
                       sum = 0;
                   }
                   if(sum_x < sum) {
                       sum_x = sum;
                   }
               }
           }      
       }
       
       return sum_x;
   }
   
   private static int hline_sum(int y) {
       int sum = 0;
       for(int x = x_s; x<=x_e; x++) {
           sum+= a[y][x];
       }
       return sum;
   }

}

문제는 2차원 NxN 격자에 숫자가 주어졌을 때, 부분 사각 격자 내부의 합의 최대값을 구하는 것. 1차원 수열의 부분 수열의 합의 최대값을 구하는 것은 매우 간단한데, 이건 꽤 경우의 수가 많아서 어렵다. 1차원의 문제를 최적한 이후에 그걸 적용하니 요구하는 속도 안에 풀렸다.

1차원의 경우에도 그냥 모든 경우 for(x1 = 0; x1 < N; x1++) for(x2 = x1; x2 < N; x2++) 에 대해 계산해도 된다. 하지만, 합의 그래프를 그려놓고 보면, sum이 음수가 되는 순간에 sum을 0으로 새롭게 세팅하고 sum을 계산하면 되겠다는 생각이 들었다. (계속 음수로 떨어지기만 하는 경우는 문제가 될 것 같지만.) 그림을 보면 더 이해가 잘 되리라 생각하여 그림을 첨부하고 더 이상의 설명은 생략한다.

see also : http://alexeigor.wikidot.com/kadane