boj23318 행렬분할

링크

23318번: 행렬분할

문제

n × m 크기의 행렬이 있다. 이 행렬을 가로로 a번, 세로로 b번 잘라 (a + 1) × (b + 1) 개의 부분으로 분할하려고 한다. 이 때, 같은 부분을 두 번 이상 자를 수는 없다. 즉, 한 개의 원소도 포함되지 않은 부분은 존재할 수 없다.

위 그림 1과 같은 6 × 7 행렬이 있을 때, 이 행렬을 가로로 2번, 세로로 3번 자르면 그림 2와 같이 된다.

분할의 '점수' 는 잘라진 각 부분의 합들 중에서 가장 큰 값으로 정의한다. 예를 들어, 그림 2와 같은 분할에서의 점수는 색칠한 부분의 합인 19이다. 최소로 분할하면 점수는 15이고, 그림은 생략한다.

행렬이 주어졌을 때 가능한 최소 점수를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 자연수 n(2 ≤ n ≤ 20)과 m(2 ≤ m ≤ 8)의 값이 주어진다. 두 번째 줄에는 자연수 a(1 ≤ a < n), b(1 ≤ b < m) 의 값이 주어진다. 세 번째 줄부터 차례로 n개의 줄에는 행렬의 원소들이 공백으로 구분되어 주어진다. 행렬의 모든 원소들은 15 이하의 자연수이다.

출력

첫 번째 줄에 최소 점수를 출력한다.

나의 풀이

브루트포스

  • dp문제지만, 범위가 작아서 combination을 계산해보니 1300백만 정도가 나왔다. 그래서 브루트포스+누적합으로도 풀 수 있을 것 같아 풀어보았다.
  • prefixSum 2차원 배열에 누적합을 계산했다. prefixSum[i][j]=prefixSum[i-1][j]+prefixSum[i][j-1]-prefixSum[i-1][j-1]+prefixSum[i][j];
  • combination으로 가로 세로 어디를 자를지 선택한 후에 가로세로 후보를 모두 뽑아내면 합 계산을 했다.
  • 부분별로 합을 계산하는데, 가로세로로 시작과 끝 변수를 만들어서 합을 계산했고, 큰값만 갱신해줬다. sum+=prefixSum[Aend][Bend]-prefixSum[Aend][Bstart]-prefixSum[Astart][Bend]+prefixSum[Astart][Bstart];
  • 2차원 for문을 나온뒤에는 answer에 더 작은 값만 갱신해 주었다.

dp

  • dp로도 풀예정이다...
  • 핵심 코드
  • 전체 코드
    package Baekjoon.java.gold;
    
    import java.io.BufferedReader;
    import java.io.InputStreamReader;
    import java.util.StringTokenizer;
    
    public class boj23318 {
        static int N,M,a,b,board[][],result[][],cutA[],cutB[],answer,prefixSum[][];
        public static void main(String[] args) throws Exception{
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st = new StringTokenizer(br.readLine());
    
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
    
            board = new int[N][M];
            result = new int[N][M];
            prefixSum = new int[N+1][M+1];
            answer = Integer.MAX_VALUE;
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            cutA = new int[a+1];
            cutB = new int[b+1];
    
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < M; j++) {
                    board[i][j]=Integer.parseInt(st.nextToken());
                    prefixSum[i+1][j+1]=board[i][j];
                }
            }
    
            for (int i = 1; i < N+1; i++) {
                for (int j = 1; j < M+1; j++) {
                    prefixSum[i][j]=prefixSum[i-1][j]+prefixSum[i][j-1]-prefixSum[i-1][j-1]+prefixSum[i][j];
                }
            }
    
            cutA[a]=N;
            cutB[b]=M;
            combiA(0,1);
    
            System.out.println(answer);
    
        }
    
        private static void combiA(int cnt, int start){
            if(cnt==a){
                combiB(0,1);
                return;
            }
    
            for (int i = start; i <= N; i++) {
                cutA[cnt]=i;
                combiA(cnt+1,i+1);
            }
        }
    
        private static void combiB(int cnt, int start){
            if(cnt==b){
                int subSum = 0;
                int N_prev=0;
                int M_prev=0;
                for (int i = 0; i < a+1;i++) {
                    M_prev=0;
                    for (int j = 0; j < b+1;j++) {
                        subSum = Math.max(getSum(N_prev,cutA[i],M_prev,cutB[j]),subSum);
                        M_prev=cutB[j];
                    }
                    N_prev=cutA[i];
                }
                answer = Math.min(subSum,answer);
                return;
            }
    
            for (int i = start; i <= M; i++) {
                cutB[cnt]=i;
                combiB(cnt+1,i+1);
            }
        }
    
        private static int getSum(int Astart,int Aend,int Bstart,int Bend){
            int sum = 0;
            sum+=prefixSum[Aend][Bend]-prefixSum[Aend][Bstart]-prefixSum[Astart][Bend]+prefixSum[Astart][Bstart];
            return sum;
        }
    }

결과

브루트포스

dp

좋은 웹페이지 즐겨찾기