[알고리즘 문제 풀기] Flow Shop(14767)

1. 문제 풀이 아이디어

• 다이나믹 프로그래밍을 활용하여 문제를 해결할 수 있다.

2. 나의 정답 코드

using System.Text;
StringBuilder sb = new StringBuilder();

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    int[] input = Array.ConvertAll(sr.ReadLine().Trim().Split(), int.Parse);
    int n = input[0];
    int m = input[1];
    int[,] p = new int[n + 1, m + 1];
    for (int i = 1; i <= n; i++)
    {
        input = Array.ConvertAll(sr.ReadLine().Trim().Split(), int.Parse);
        for (int j = 1; j <= m; j++)
        {
            p[i, j] = Math.Max(p[i - 1, j], p[i, j - 1]) + input[j - 1];
        }
        sb.Append($"{p[i, m]} ");
    }
    sw.WriteLine(sb);
}

3. 정리

• p[i, j]는 (i, j)까지 이동할 수 있는 최대 합이 된다.

• p[i, j] = max(위쪽, 왼쪽) + 현재 칸 값으로 점화식을 세워 계산한다.

• p[i, m]은 최종 시간이 되며, 각 값을 출력하여 문제를 해결한다.