[백준] 9465번 - 스티커

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

9465번: 스티커

---

DP를 이용해서 풀면 되는 문제다!

 

dp[i][j]는 i행 j열까지의 스티커를 떼어냈을 떄 얻을 수 있는 최대 점수를 저장하면 된다

 

이 때 인접한 스티커는 떼지 못하기 때문에 위의 그림처럼 대각선으로만 뗴어낼 수 있다

또 3칸이상 비교를 하게 되면 스티커를 뗴지 않은 칸이 발생하기 때문에 저렇게 색칠한 두 가지 중 큰 값을 골라 뗴면 된다

 

그리고 실제로 구현할 떄는 위의 점화식처럼 1칸 뒤와 2칸 뒤 중 큰 값을 선택해서 뗴어내면 된다!

 

 

---

 

자바 코드)

package boj;

import java.util.Scanner;

public class boj9465 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while(t>0) {
            t--;
            int n = scanner.nextInt();
            int[][] arr = new int[2][n+1];
            int[][] dp = new int[2][n+1];
            for(int i=0;i<2;i++) {
                for(int j=1;j<=n;j++) {
                    arr[i][j] = scanner.nextInt();
                }
            }

            dp[0][1] = arr[0][1];
            dp[1][1] = arr[1][1];
            for(int j=2;j<n+1;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]));
        }
    }
}

---

참고)

https://loosie.tistory.com/451

[BOJ] 백준 9465번 스티커 (Java)