DP

백준 9465번을 Java를 이용해 풀어보았다. 결국 또 못 풀었다. DP 죽이고 싶다.

문제 링크 첨부한다.
https://www.acmicpc.net/problem/9465

DP 이용해서 각 위치별 최댓값 갱신하기

이런 원리로 끝까지 계산해나가며 마지막 column의 위 아래 두 칸 중에 더 큰 녀석을 출력하면 된다. 이를 코드로 표현하면 다음과 같다.

Integer solution(){
        int[][] dp = new int[2][N+1];
        dp[0][1] = map[0][1];
        dp[1][1] = map[1][1];

        for(int i=2; i<=N; i++){
            dp[0][i] = Math.max(dp[1][i-2], dp[1][i-1]) + map[0][i];
            dp[1][i] = Math.max(dp[0][i-2], dp[0][i-1]) + map[1][i];
        }

        return Math.max(dp[0][N], dp[1][N]);
    }

전체 코드는 아래와 같다.

import java.io.*;
import java.util.StringTokenizer;

public class boj9465 {
    static int T,N;
    static int[][] map;

    static Integer solution(){
        int[][] dp = new int[2][N+1];
        dp[0][1] = map[0][1];
        dp[1][1] = map[1][1];

        for(int i=2; i<=N; i++){
            dp[0][i] = Math.max(dp[1][i-2], dp[1][i-1]) + map[0][i];
            dp[1][i] = Math.max(dp[0][i-2], dp[0][i-1]) + map[1][i];
        }

        return Math.max(dp[0][N], dp[1][N]);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk;
        T = Integer.parseInt(bfr.readLine());

        for(int t=0; t<T; t++){
            N = Integer.parseInt(bfr.readLine());
            map = new int[2][N+1];
            for(int i=0; i<2; i++){
                stk = new StringTokenizer(bfr.readLine());
                for(int j=1; j<=N; j++){
                    map[i][j] = Integer.parseInt(stk.nextToken());
                }
            }
            System.out.println(solution());
        }
    }
}

이 블로그의 풀이를 참조해 풀었다.

결국 점화식...ㅠ... 으악..!!!