[백준] 9465 스티커 - DP JAVA

https://www.acmicpc.net/problem/9465

9465번: 스티커

코드설명

DP 문제입니다.

 

이전에 풀었던 계단 오르기 문제와 비슷하다고 느꼈습니다.

시작점에서 dp를 생각하지 않고, 이미 이동할 위치에서 이전의 위치를 선택해야합니다.

 

5
50 10 100 20 40
30 50 70 10 60

위의 문제로 예로들면, 여기서 arr의 시작은 arr[0][1] ~ arr[0][5] 를 의미합니다.

arr[0][2] 가 있다고 가정합니다. 예시에서의 값은 arr[0][2] = 10입니다.

이때 arr[0][2] 가 될 수 있는 값은 arr[1][1] 밖에 없습니다. 

arr[0][3] 으로 이동해봅니다. 

이때 arr[0][3] 이 될 수 있는 값은 arr[1][2]와 arr[1][1] 입니다.

위의 값들의 최대값( Math.max(arr[1][2], arr[1][1]) + arr[0][3] 들을 비교하여 이동시키면 됩니다. 

 

처음에는 dp[0][0] 으로 처리할려고생각하였지만,

각 스티커의 위치에서 열 기준으로 2개까지 이동할 수 있기에 연산의 처리를 위하여 dp[0][0] 은 0 으로 선언하고 진행합니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;

public class Main {
	public static int T, N, M;
	public static int answer = 0;
	public static int[][] arr;
	public static int[][] dp;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	T = Integer.parseInt(st.nextToken());
    	
    	for(int i=0;i<T;i++) {
    		st = new StringTokenizer(br.readLine());
    		N = Integer.parseInt(st.nextToken());
    		
    		arr = new int[2][N+1];
    		dp = new int[2][N+1];
    		
    		for(int j=0;j<2;j++) {
    			st = new StringTokenizer(br.readLine());
    			for(int k=1;k<=N;k++) {
        			arr[j][k] = Integer.parseInt(st.nextToken());    				
    			}
    		}
    		
    		dp[0][1] = arr[0][1];
    		dp[1][1] = arr[1][1];
    		
    		for(int j=2;j<=N;j++) {
    			dp[0][j] = Math.max(dp[1][j-1], dp[1][j-2]) + arr[0][j];
    			dp[1][j] = Math.max(dp[0][j-1], dp[0][j-2]) + arr[1][j];
    		}
    		
    		System.out.println(Math.max(dp[0][N], dp[1][N]));
    	}
    	
    }
    
}