백 준 - 11066

 

문제 주소 : www.acmicpc.net/problem/11066

11066번: 파일 합치기

 

문제는 다음과 같습니다.

문제에서 구하고자 하는 것은 각 케이스에 따라서 한 행을 출력하는데 모든 장을 합치는데 필요한 최소 비용을 구하고자 하는 것입니다.

 

문제의 방향은 다음과 같습니다.

먼저 전체 파일을 비용을 합치는데 있어서 다양한 경우가 존재한다는 것을 예시를 통해서 파악을 할 수 있었습니다.

근데 여기서 전체경우를 알아보는 브루트포스를 이용해서 최소비용을 탐색한다면 문제의 시간제한을 지킬 수 없을 것 같았습니다.

따라서 저는 여기서 불필요한 계산을 방지하고 이를 위해서 메모리제이션을 활용한 동적계획법을 이용하는 것으로 문제 해결의 방향을 정하였습니다.

 

방향은 다음과 같습니다.

 

정리하자면 동적계획법을 이용하기 위해서 먼저 전체 파일을 합치기 이전에 파일의 부분을 합치는 비용을 파악해서 저장하는 배열이 필요하고 이를 위해서 일종의 점화식이 필요합니다,

 

저는 파일의 i쪽에서부터 j 쪽 까지 파일을 합치는 최소 비용을 점화식으로 설정하였습니다.

따라서 2차원 배열 D를 만들어주고 점화식에 맞게 값을 구하면서 저장하면됩니다.

 

파란색 글씨로 된 것이 점화식 부분인데 여기서 D[k+1][j] 는 D[i][j] 보다 아래의 행에 있는 값을 가져와야 하므로 맨 아래 행에서 부터 시작해야 합니다. 그리고 구한 저 많은 경우에 대해서 최소 비용을 찾아서 저장하는 것입니다.

 

전체적인 코드는 다음과 같습니다.

public class Main {

    //문제 11066

    public static void main(String[] args) {

        Scanner stdin = new Scanner(System.in);

        int t = stdin.nextInt();

        for (int i = 0 ; i < t ; i++) {

            int n = stdin.nextInt();
            int[] arr = new int[n];
            int[] sum = new int[n+1];

            for(int j = 0 ; j < arr.length ; j++) {

                arr[j] = stdin.nextInt();

                sum[j+1] += sum[j] + arr[j];
            }

            int val = getMinValue(arr , sum);

            System.out.println(val);

        }
    }

    //i ~ j 까지의 구간의 최소 파일 합치기 비용으로 점화식을 정의
    //2차원 배열을 사용해야 한다.

    public static int getMinValue(int[] arr , int[] sum) {

        int[][] D = new int[arr.length][arr.length];

        for (int i = D.length-2 ; i >=0 ; i--) {

            for(int j = i+1 ; j < D.length ; j++) {

                if(i+1 == j) {

                    D[i][j] = sum[j+1] - sum[i];
                }
                else {

                    D[i][j] = Integer.MAX_VALUE;

                    for(int k = i ; k < j ; k++) {

                        int num = D[i][k] + D[k+1][j] + sum[j+1] - sum[i];

                        D[i][j] = Math.min(D[i][j] , num);

                    }
                }
            }
        }


        return D[0][arr.length-1];
    }

}