백준 9465) 스티커 java

분석

---

스티커를 떼어내면 맞붙어 있는 스티커는 못쓴다고 했으므로 각 스티커당 경우의 수는 두가지이다.

 

1.여기 스티커를 떼면	3.여기 불가능	5.경우의 수 포함 x
2.여기 불가능	4.여기 가능(경우1)	6.여기 가능(경우2)

예를 들어 1번 스티커를 떼면 4번 스티커 , 6번 스티커를 뗄 수 있다.

5번은 경우의 수에 포함시키 않았는데 1-> 4 ->5 로 가는 경로가 결국 4번 경로와 겹치지 때문이다.

 

다음으로 고려해야 할 것은 마지막 열의 스티커는 무조건 선택된다는 것이다.

 

이 조건들을 종합적으로 생각해보았을 때 결국 마지막에 어떤 스티커가 골라졌을 때 제일 클지를 비교해봐야한다.

 

점화식)

dp[row][col]      = dp[row+1][col-1]+price[row][col],  dp[row+1][col-2]+price[row][col]  // 대각선 아래 1칸과 대각선 아래 2칸을 비교한다.

dp[row+1][col]  = dp[row][col-1]+price[row][col],  dp[row][col-2]+price[row][col]  // 대각선 위 1칸과 대각선 위 2칸을 비교한다.

 

마지막 열에서 나온 dp  값이 큰 것을 값으로 출력하면 된다 !

코드

---

import java.util.Scanner;

import static java.lang.Math.max;


public class Main {

    static int[][] dp;
    static int[][] price;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cnt = sc.nextInt();
        int num=0;
        for (int i = 0; i < cnt; i++) {
            num = sc.nextInt();
            dp = new int[2][num + 1];
            price = new int[2][num + 1];

            for (int j = 0; j < 2; j++) {
                for (int k = 1; k <= num; k++) {
                    price[j][k] = Integer.parseInt(sc.next());
                }

            }
            dp[0][1] = price[0][1];
            dp[1][1] = price[1][1];
            dp(num);
            System.out.println(max(dp[0][num],dp[1][num]));
        }



    }

    static void dp(int num) {

        for (int i = 2; i <= num; i++) {
            dp[0][i] = max(dp[1][i-1] + price[0][i],dp[1][i-2] + price[0][i]);
            dp[1][i] = max(dp[0][i-1] + price[1][i],dp[0][i-2] + price[1][i]);
        }
    }

}