[java 백준] 실버2 /9465번 스티커

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

9465번: 스티커

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

 

이 문제는 도저히 어떻게 해야할지 몰라서 다른 사람들의 코드를 참고했다. 예를 들어 dp[1][3]을 구할 때,

위의 사진처럼 가짓수는 2가지이다. 50에서 바로 70으로 가는 법이 있고, 10에서 70으로 가는 법이 있는데 이 경우는 30을 지나야한다.

 

나는 10에서 가는 방법은 생각했는데, 50에서 가는 방법은 생각하지 못했다.

어쨋든 중요한건 대각선으로 가야한다는 것이다.

 

열이 1부터 시작하므로,

dp[0][1] = arr[0][1];

dp[1][1] = arr[1][1];

 

위 코드 처럼 1열은 초기화시켜주는 코드로 작성한다. 

 

대각선으로 가는 방법은 아래코드를 사용하면 된다.

for (int a = 2; a <= n; a++) {

                dp[0][a] = Math.max(dp[1][a - 1], dp[1][a - 2]) + arr[0][a];

                dp[1][a] = Math.max(dp[0][a - 1], dp[0][a - 2]) + arr[1][a];

}

dp[1][3] 처럼 무조건 어딘가를 경유해 간다고 해서 값이 커지는게 아니다. 10의 경우 10->30 이므로 총합은 40이지만 50에서 바로 arr[1][3]으로 가면 총합이 50이기 때문이다.

 

아무튼 dp너무 어렵다...ㅜ 점화식 세우는 것도 어렵다. 그치만 뭐든 처음부터 잘되는 것은 없으니 더 많이 공부해서 실력을 쌓아야겠다!!

 

참고한 사이트 

---

https://fbtmdwhd33.tistory.com/76

[백준,BOJ 9465] 스티커( JAVA 구현)