L - Deque / atcoder.jp

문제링크 : https://atcoder.jp/contests/dp/tasks/dp_l
문제해설 : https://jinpyo.kim/EducationalDP-solution
Submission : https://atcoder.jp/contests/dp/submissions/9546944
Java source : https://github.com/skysign/WSAPT/blob/master/atcoder.jp/L%20-%20Deque/src/Main.java

리스트가 주어지고, 두 플레이어가, 이 리스트의 가장 앞/뒤 중에 하나를 서로 빼게 됩니다. 플레이어 타로/지로에 따라서, 뺀수는 타로는 X, 지로는 Y에 더하게 되구요, X-Y 값을 찾는 문제입니다.

문제를 풀기에서 앞서서, 타로와 지로가 숫자를 선택하는 전략은 동일하는 것을 알 수 있습니다.

• 타로는 X-Y 가 최대값이 되기 위한 선택을 한다
• 지로는 X-Y 가 최소값이 되기 위한 선택을 한다
• 타로가 리스트 앞/뒤에서 한 숫자를 꺼낸뒤, 꺼낸 숫자의 합 X
• 지로가 리스트 앞/뒤에서 한 숫자를 꺼낸뒤, 꺼낸 숫자의 합 Y

위의 4가지를 다시 정리하면

• 타로는 X가 최대가 되도록 선택
• 지로는 Y가 최대가 되도록 선택

따라서, 타로/지로 모두 같은 방식으로 리스트에서 앞/뒤 숫자중에 더 큰 숫자를 선택하게 됩니다.
여기서, 타로가 한번 해서 X를 계산하고, 지로가 한번 하고 Y를 계산하고, 하는 방식이 아니라, X-Y를 한번에 계산하는 방식으로 방향을 잡아야 합니다. 왜냐하면, 둘이 숫자를 선택하는 전략은 같기 때문입니다.

저는 Sample Input 5을 분석하다가, 처음 이 문제를 풀 때, Recursion을 사용하여 문제를 풀었습니다. 답은 나오지만, Submission하면, 2초 제한시간을 넘겨서, time out이 됩니다.
Sample input 5번의 타로의 2번째 선택에서 _2, 9, 7, 1_이 남았을 때, 2가 아닌 1을 선택하게 됩니다. 여기서 Recursive방식이 맞나? 라고 잘 못 생각했는대, 이 문제도 DP문제인 만큼 Recurrence relation으로 풀이가 가능합니다.

리스트 as가 문제의 정의에 따라서, 아래와 같이 주어짐니다.
(문제에서는 a라고 표기 하지만, 코드와 같은 변수이름을 쓰겠습니다.리스트라는 의미에서 s를 붙이겠습니다.)
\begin{aligned}
1 \leq i \leq N \\
as = a_1 ... a_N \\
\end{aligned}

as가 있는 상태에서 앞 or 뒤 에서 하나씩 뺀다고 생각하면, Recusive방식을 사용해서 문제를 푸는 쪽으로빠지기 쉽습니다.
(저도 그랬구요. - -; 코드가 궁금하시면 여기 참고
답은 나오지만, Submission하면 timeout 입니다.
Submission 결과가 궁금하시면 여기 참고

반대로 생각해서 as 를 a_1 부터 하나씩 더해서 a_N까지 만들어 간다고 생각하는 것이, 이 문제를 DP로 풀기위한 올바른 접근입니다.

첫번째 고른 경우, as에는 a_1 한개만 있습니다.
\begin{aligned}
dp_1 = a_1 \\
X = a_1 \\
Y = 0 \\
\end{aligned}

두번째 아이템을 as에 추가합니다. a_1과 a_2가 두개 있습니다.
dp_2는 2가지 선택이 가능합니다. a_1과 a_2를 선택할 수 있습니다. 문제의 정의에 따라서, 타로는 a_1과 a_2중에 큰 값을 타로는 선택해야 합니다. a_1이 크다고 가정합니다.
\begin{aligned}
dp_2 = Max(a_1, a_2) = a_1 \\
X = a_1 \\
Y = a_2 \\
X-Y = a_1 - a_2
\end{aligned}

dp_2의 식에 Y를 대입해보면, 위의 dp_2식을 아래와 같이 바꿔 볼 수 있습니다.
a_1과 a_2 둘중에 어떤것이 큰지 결정해야 한다고 하면, 아래와 같습니다.
\begin{aligned}
dp_2 = Max(a_1 - a_2, a_2 - a_1) \\
dp_2 = Max(a_1 - Y, a_2 - Y)
\end{aligned}

• X 가 a_1 이면, Y는 a_2
• X 가 a_2 이면, Y는 a_1

위에서는 dp_2 가 두번째 아이템을 as에 넣을 때, 각각 X-Y의 최대값입니다.
dp_2를 고처써 보면, dp_1,2 로, 첫번째 아이템부터, 두번째 아에템까지 고려 했을 때, X-Y의 최대값으로 정의해 볼 수 있습니다.
\begin{aligned}
dp_{1,2} = Max(a_1 - Y, a_2 - Y) \\
\end{aligned}
dp_{1,2}는 a_1 ~ a_2까지 고려한 경우 임으로, 문제의 정의에 따라서,

• 리스트의 앞을 deque 하면 X는 a_1, Y는 a_2
• 리스트의 뒤을 deque 하면 X는 a_2, Y는 a_1

Recurrence relation이 완성되려면, Y 가 dp_{?,?}형태로 바뀌어야 합니다. 왜냐하면, 문제에서 항상 제일 앞 or 뒤를 꺼내는 것이 문제의 정의 이기 때문에, 위의 식에서 이미, dp_{1,2}일 때, 가장 앞에 있는 수 a_1, 가장 뒤에 있는 수 a_2를 꺼내고 있습니다.

X에 a_1을 선택해서 넣게 되면, Y가 a_2가 됩니다. 따라서, dp_{2,2} 즉, a_2만 있는 as 에서 a_2 선택되는 경우, X - Y = a_2 - 0 = a_2 가 되구요, Y를 dp_{2,2}로 바꿀 수 있습니다.

반대로, X가 a_2를 선택하게 되면, Y는 dp_{1,1} 즉, a_1만 있는 as에서 a_1이 선택되어는 경우, X - Y = a_1 - 0 = a_1 이 됩니다.

위의 2문장을 식으로 바꿔보면, 아래와 같습니다.
\begin{aligned}
dp_{1,2} = Max(a_1 - dp_{2,2}, a_2 - dp_{1,1}) \\
\end{aligned}

dp_{1,2}에서 1을 i로 바꾸고, 2를 j로 바꿔 보면, 아래와 같습니다.
\begin{aligned}
dp_{i,j} = Max(a_i - dp_{i+1,j}, a_j - dp_{i,j-1}) \\
\end{aligned}

2차원 배열의 순서에 따라서, Max()의 인자 순서만 바꾸겠습니다.
\begin{aligned}
dp_{i,j} = Max(a_j - dp_{i,j-1}, a_i - dp_{i+1,j}) \\
\end{aligned}

Max()를 계산하는대 필요한 2가지 dp_{1,2}를 계산하는대 필요한 dp 값은 dp_{1,1}과 dp_{2,2}입니다.

N이 4라고 하면, dp_{i,j} 단, i==j 인 경우는, a_i와 값이 같습니다. 이부분의 위에서 설명했구요.

위의 그림과 배열을 대각선 방향으로 3번 계산해야 합니다. 계산하는 순서는 아래와 같구요,
각 선에서 계산된 값은 다음 선을 계산하는대 입력값으로 사용됩니다.

• 빨간색 선
• 파란색 선
• 노란색 선

답은 dp_{1,N}입니다. 이제 코드를 보면 아래와 같습니다.

import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        Main main = new Main();
        main.solve();
    }

    public void solve() throws IOException {
//        Scanner sc = new Scanner(System.in);
        Reader sc = new Reader();
        int N = sc.nextInt();
        long[] as = new long[N+1];

        for(int i=1; i<=N; ++i) {
            as[i] = sc.nextLong();
        }

        long[][] dp = new long[N+1][N+1];

        // d_{i,j} i와 j가 서로 같은 경우
        // d_{2,2}는 as_2와 같음
        for(int i=0; i<dp.length; ++i) {
            dp[i][i] = as[i];
        }

        for(int d_ij=1; d_ij<N; ++d_ij) {
            for(int k=1; k<=N; ++k) {
                int i = k;
                int j = i+d_ij;
                if(j<=N) {
//                    System.out.printf("%dx%d ", i, j);
                    dp[i][j] = Math.max(as[i] - dp[i+1][j], as[j] - dp[i][j-1]);
                }
            }
//            System.out.printf("\n");
        }

        System.out.println(dp[1][N]);
    }

    // https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/
    class Reader
    {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String nextLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1)
            {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            }  while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');

            if (c == '.')
            {
                while ((c = read()) >= '0' && c <= '9')
                {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }
}