공부 137일차: 백준 9465번 스티커 자바 java

9465 스티커

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

9465번: 스티커

 

 

 

 

---

백준 9465번 문제 스티커

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

	[0][i]	[0][i+1]	[0][i+2]	[0][i+3]
[1][i-1]	[1][i]	[1][i+1]	[1][i+2]

 

	[0][i]	[0][i+1]	[0][i+2]
[1][i-1]	[1][i]	[1][i+1]

위 예시처럼 [1][i]를 선택할 경우 줄로 그은 왼쪽오른쪽위의 것들은 자동적으로 무조건 선택할 수 없고,

선택권을 가지는 건 빨간색으로 표시한 부분 뿐이다

(둘 중 어떤 것을 삭제하느냐에 따라 또 뗄 수 있는 스티커의 상황이 달라지기 때문이다)

따라서 +1 대각선과 +2 대각선 중 하나를 선택하면 되겠다

다만 dp는 작은 것부터 구하므로 먼저 구해진 -1, -2의 대각선값을 비교하면 된다

 

https://squareyun.tistory.com/5

감은 잡히는데 명확하진 않아서 여러 글을 보다가 이 블로그를 참조했다

 

최종 점화식은

dp[0][j] = Math.max(dp[1][j-1], dp[1][j-2]) + 그자리점수
dp[1][j] = Math.max(dp[0][j-1], dp[0][j-2]) + 그자리점수

이 된다

 

 

 

---

정답 인정 코드

---

 

import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int t = Integer.parseInt(br.readLine());
        
        for(int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            // 2행이므로 2차원배열 중 한쪽의 크기는 2
            int[][] arr = new int[2][n];
            int[][] dp = new int[2][n+1];
            
            for(int j = 0; j < 2; j++) {
                st = new StringTokenizer(br.readLine());
                for(int k = 0; k < n; k++) {
                    // 주어진 스티커 점수 2차원 배열에 넣기
                    arr[j][k] = Integer.parseInt(st.nextToken());
                }
            }
            
            // 디버깅 System.out.println(Arrays.deepToString(arr));
            
            // 맨왼쪽 값으로 초기화
            dp[0][1] = arr[0][0];
            dp[1][1] = arr[1][0];
            
            for(int j = 2; j < n+1; j++) {
                dp[0][j] = Math.max(dp[1][j-1], dp[1][j-2]) + arr[0][j-1];
                dp[1][j] = Math.max(dp[0][j-1], dp[0][j-2]) + arr[1][j-1];
            }
            
            System.out.println(Math.max(dp[0][n], dp[1][n]));
        }
    }
 
}

 

arr은 0부터 시작하기 때문에 j-1로 표시했다

 

 

 

---

설명하기 참 어려운 문제 같다