백준/11066번/파일 합치기/골드3

Problem Link: https://www.acmicpc.net/problem/11066

문제 설명

Site: Baekjoon
Number: 11066
Category: Dynamic Programming
Rank: Gold 3

주어진 숫자들을 연속적인 것들을 합할 때 마다 그 숫자 합 만큼 비용이 발생할 때, 모든 숫자를 합치는 과정에서 나오는 비용의 최솟값을 구하는 문제입니다.

여러 숫자가 합쳐지는 과정은 전체적인 순서에서 어디든 발생할 수 있기 때문에 순차적으로 계산하는 1차원 DP로는 계산할 수 없어 2차원 DP를 사용하여야 해결할 수 있습니다.

문제 풀이

숫자들을 합할 때 마다 총 숫자의 합 만큼 발생하는 비용을 더해주기 위해 누적합을 저장하는 Sum배열과 2차원 DP배열 그리고 Page의 값을 저장하는 배열을 선언합니다.

각 테스트케이스 마다 다음과 같은 과정을 반복합니다.

1. Page값을 모두 읽고 Pages배열과 Sum배열 값에 저장합니다.

2. DP[i][i+j] 값을 계산하기 전에 최솟값으로 비교해야 함으로 INF값으로 초기화 합니다.

3. DP 배열을 for문을 삼중으로 진행하며 다음과 같은 방식을 통해 최솟값을 갱신합니다.

   DP[i][i+j]의 의미는 Pages의 i번째 원소부터 i+j번째 원소까지 합친 과정에서 발생한 비용의 최솟값을 의미합니다.

   모든 구간에서 모든 범위만큼의 계산을 작은 범위 부터 키워나가 최솟값을 갱신하는 방식입니다.

   j는 파일들을 합하는 범위를 나타내며, i는 검사하는 파일의 시작 순서, k는 j만큼의 범위에서 좌우로 잘라 계산하는 범위를 나타냅니다. 예) i = 2, j = 5, k = 2인 상황은 다음과 같습니다.

   

4. 모든 i, j, k의 범위를 돌면 모든 구간과 범위에서 최솟값이 DP[1][K]에 저장됩니다.

#include <iostream>

using namespace std;

int Pages[502];
int Sum[502];
int DP[502][502];

#define INF 2147483647

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int T;
    cin >> T;

    while(T--)
    {
        int K;
        cin >> K;

        for(int i = 1; i <= K; i++)
        {
            cin >> Pages[i];
            Sum[i] = Sum[i - 1] + Pages[i];
        }

        //검사하는 범위
        for(int j = 1; j < K; j++)
        {
          //검사 시작 구간
	        for(int i = 1; i <= K - j; i++)
	        {
            DP[i][i + j] = INF;

            //어디서 좌우로 나눌지 정하는 범위
		        for(int k = i; k < i+j; k++)
		        {
                    DP[i][i + j] = min(DP[i][i + j], DP[i][k] + DP[k + 1][i + j] + Sum[i + j] - Sum[i - 1]);
		        }
	        }
        }

        cout << DP[1][K] << '\n';
    }


    return 0;
}