C - Vacation / atcoder.jp

문제 링크 : https://atcoder.jp/contests/dp/submissions/9157155
답 링크(속도 최적화 하기전) : https://atcoder.jp/contests/dp/submissions/9157155
답 링크(속도 최적화된) : https://atcoder.jp/contests/dp/submissions/9157155
자바 코드 : https://github.com/skysign/WSAPT/blob/master/atcoder.jp/C%20-%20Vacation/src/Main.java

문제 정의에 따라서 a, b, c 를 아래와 같이 가정하고,

\begin{aligned}
a = 0, b = 1, c = 2 \\
1 \leq N \leq 10^5 \\
(1 \leq i \leq N) \\
dp[i][a] = max(dp[i-1][b], dp[i-1][c]) + act[i][a] \\
dp[i][b] = max(dp[i-1][a], dp[i-1][c]) + act[i][b] \\
dp[i][c] = max(dp[i-1][a], dp[i-1][b]) + act[i][c] \\
\end{aligned}

마지막에 dp[i][0~2] 중에서 가장 최대값을 선택합니다.

    import java.util.Scanner;

    public class Main {
        static int N;
        static int[][] act;
        static int[][] dp;
        static int r;

        static int a = 0;
        static int b = 1;
        static int c = 2;

        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            N = sc.nextInt();

            act = new int[N+1][3];
            dp = new int[N+1][3];
            for(int i=1; i<=N; ++i) {
                act[i][a] = sc.nextInt();
                act[i][b] = sc.nextInt();
                act[i][c] = sc.nextInt();
            }

            for(int i=1; i<=N; ++i) {
                dp[i][a] = Math.max(dp[i-1][b], dp[i-1][c]) + act[i][a];
                dp[i][b] = Math.max(dp[i-1][a], dp[i-1][c]) + act[i][b];
                dp[i][c] = Math.max(dp[i-1][a], dp[i-1][b]) + act[i][c];
            }

            r = Math.max(dp[N][a], dp[N][b]);
            r = Math.max(r, dp[N][c]);
            System.out.println(r);
        }
    }