백준 알고리즘 11066번 파일합치기

동적계획법(Dynamic Programming)

말 그대로 파일을 합치기 위해 가장 최소가되는 비용을 찾는 문제이다

예시 처럼 40,30,30,50 일경우

방법 1. 40,{30,30,50}

방법 2. 40,{{30,30},50}

방법 3. 40.{30,{30,50}}

방법 4. {40,30},{30,50}

방법 5. {40,30,30},{50}

방법 6. {{40,30},30},{50}

방법 7. {40,{30,30}},{50}

이런 식으로 문제를 해결하되 이중 최소의 값을 출력 값으로 선택한다.

(소스와 위의 방법의 예제와는 순서가 다를 수 있습니당)

사실, 인터넷을 통해 참고 했지만 소스를 이해하는데도 내것으로 만드는데도 많은 시간과 어려움이 있었다.

아직 너무 실력이 없기 때문에 다른 분들도 슬퍼하지말고 같이 열심히 합시다!

 
static final int MAX = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {

        int T; // TC
        int K; // 소설을 구성하는 장의 수
        int[] C; // 각 장의 파일 크기
        int[] S;
        int[][] dp; // i번째 수 부터 j번째 수 까지 수를 합치는 데 필요한 최소 비용

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());

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

            K = Integer.parseInt(br.readLine());
            C = new int[K + 1];
            S = new int[K + 1];
            dp = new int[K + 1][K + 1];

            S[0] = 0;
            // input & initialize
            // k 원소의 개수
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 1; i < K + 1; i++)
            {
                C[i] = Integer.parseInt(st.nextToken());
                // C의 누적합
                S[i] = S[i - 1] + C[i];
                for (int j = 1; j < K + 1; j++)
                {
                    // 최소값을 구해야하므로 초기값으로 MAX값을 설정한다.
                    dp[i][j] = MAX;
                }
            }
            System.out.println(solve(dp, C, S,1, K));
        }
    }

    static int solve(int[][] dp, int[] C, int[] S, int start, int end)
    {

        // 자기 자신인 경우 합치는 비용은 0
        if (start >= end)
        {
            return 0;
        }
        // 이웃한 경우
        if (end == start + 1)
        {
            return C[start] + C[end];
        }

        for (int i = start; i < end; i++)
        {
            int temp = solve(dp, C, S, start, i) + solve(dp, C, S, i + 1, end) + S[end] - S[start - 1];
            dp[start][end] = Math.min(dp[start][end], temp);
        }
        return dp[start][end];
    }