백준 9465 - 스티커 [DP/JAVA]

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

 

DP문제이다. 런타임에러 때문에 애를 좀 먹었으나 풀이는 어렵지 않다.

---

사고방식

열을 기준으로 생각해보자. 

arr[i][j]에는 입력값. 즉, 스티커의 점수를 받아주고, 

dp[i][j]에는 i,j 위치에 도달할 때까지의 최고 점수를 넣는다. 즉, 

1,1	1,2	1,3	1,4	1,5
2,1	2,2	2,3	2,4	2,5

dp 배열의 1,3 위치(dp[1][3]) 에는 arr (1,1), (2,2), (1,3)의 합이나 arr (2,1), (1,3)의 합 중 큰 값이 들어간다. 

문제에서 

5

50 10 100 20 40

30 50 70 10 60

을 주었으므로 이를 예로 들자면 dp[1][3]은 50+50+100 혹은 30+100 중 큰 값이 들어간다.

이를 점화식으로 표현하면 

dp[1][3] = Math.min(dp[2][2], dp[2][1])+arr[1][3] 이다. (dp[2][2]인 이유는 arr[1][1] + arr[2][2]가 dp[2][2]이기 때문이다.)

i 값이 2인 dp[2][j]들도 같은 방식이다.

 

일반화하면 

dp[1][j] = Math.min(dp[2][j-2], dp[2][j-1]) + arr[1][j] 

dp[2][j] = Math.min(dp[1][j-2], dp[1][j-1]) + arr[2][j]

---

결론

(위에서는 설명을 위해 i,j를 행,열에 이용하였으나 실제 문제를 풀 때는 행에 변수를 넣어줄 일이 없어서 열에 i를 이용했다.) 

dp[1][i] = Math.max(dp[2][i-2], dp[2][i-1]) + arr[1][i]

dp[2][i] = Math.max(dp[1][i-2], dp[1][i-1]) + arr[2][i]

 

import java.util.Scanner;
 
public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for(int a=1; a<=t; a++){
            int n = sc.nextInt();
            int arr[][] = new int [3][n+1];
            for(int i=1; i<=n; i++){
                arr[1][i] = sc.nextInt();
            }
            for(int i=1; i<=n; i++){
                arr[2][i] = sc.nextInt();
            }
            
            int dp[][] = new int [3][n+1];
            
            dp[1][1] = arr[1][1];
            dp[2][1] = arr[2][1];
            
            for(int i=2; i<=n; i++){
                dp[1][i] = Math.max(dp[2][i-2], dp[2][i-1]) + arr[1][i];
                dp[2][i] = Math.max(dp[1][i-2], dp[1][i-1]) + arr[2][i];
            }
            System.out.println(Math.max(dp[1][n], dp[2][n]));            
        }
    }
}