[BOJ] 11066번 파일 합치기

복기

문제를 해결하기 위해 어떤 순서로 답을 구해야 할지 고민하자.

코드

• C++ 17

#include <stdio.h> #include <memory.h>   #define INF 987654321 #define MIN(a, b) ((a) < (b) ? (a) : (b))   int T, K;   // Sums[i] : 챕터 i까지의 비용의 총합 // 총 비용은 Sums의 값으로 이뤄진다. int Sums[501];   // Memo[i][j] : 챕터 i부터 챕터 j까지 합치는 데 총 비용 중 최소값 // 점화식 : Memo[i][j] = Memo[i][k] + Memo[k + 1][j] int Memo[501][501];   int main() {     scanf("%d", &T);     while (T--)     {         scanf("%d", &K);         for (int i = 1; i <= K; ++i)         {             int num;             scanf("%d", &num);             Sums[i] = Sums[i - 1] + num;         }           for (int j = 1; j < K; ++j)         {             for (int i = 1; i <= K - j; ++i)             {                 Memo[i][i + j] = INF;                 for (int k = i; k < i + j; ++k)                     Memo[i][i + j] = MIN(Memo[i][i + j], Memo[i][k] + Memo[k + 1][i + j]);                 Memo[i][i + j] += Sums[i + j] - Sums[i - 1];             }         }           printf("%d\n", Memo[1][K]);     } }

• C# 6.0

using System; using System.Collections.Generic; using System.Security.Cryptography.X509Certificates;   namespace Csharp {     class Program     {         static int T, K;         static int[] Sums = new int[501];         static int[,] Memo = new int[501, 501];           static void Main(string[] args)         {             T = Convert.ToInt32(Console.ReadLine());             while (T --> 0)             {                 K = Convert.ToInt32(Console.ReadLine());                 var inputs = Console.ReadLine().Split();                 for (int i = 1; i <= K; ++i)                     Sums[i] = Sums[i - 1] + Convert.ToInt32(inputs[i - 1]);                                  for (int j = 1; j < K; ++j)                 {                     for (int i = 1; i <= K - j; ++i)                     {                         Memo[i, i + j] = int.MaxValue;                         for (int k = i; k < i + j; ++k)                             Memo[i, i + j] = Math.Min(Memo[i, i + j], Memo[i, k] + Memo[k + 1, i + j]);                         Memo[i, i + j] += Sums[i + j] - Sums[i - 1];                     }                 }                   Console.WriteLine(Memo[1, K]);             }         }     } }

• Python 3

# 해결하지 못했다.