[백준/JAVA] 9465번: 스티커

📖 문제

9465번: 스티커

 

 

 

💡  풀이 방식

• DP

1. dp 배열을 만든다. (dp[i][j] : 해당 칸 (i, j)까지 스티커를 떼었을 때 얻을 수 있는 최대 점수)

   2. 0번 열은 본인이 최대이므로 본인으로 초기화한다.

   3. 1번 열은 특수처리한다.

• [0][1]은 왼쪽 아래 값과 본인 칸 값 더하기
• [1][1]은 왼쪽 위쪽 값과 본인 칸 값 더하기

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

 

 

   4. 2번 열부터 뒤쪽까지는 아래와 같은 방식으로 채운다..

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

 

 

 5. 마지막 열의 두 값 중 큰 값을 구해 출력한다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        StringBuilder sb = new StringBuilder();
        
        int T = Integer.parseInt(br.readLine());
        while(T --> 0) {
            int n = Integer.parseInt(br.readLine());
            int[][] arr = new int[2][n];
            int[][] dp = new int[2][n];
            
            for(int i = 0 ; i < 2 ; i++) {
                st = new StringTokenizer(br.readLine());
                for(int j = 0 ; j < n ; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            
            // 0번 열은 본인이 최대이므로 본인으로 초기화
            dp[0][0] = arr[0][0];
            dp[1][0] = arr[1][0];
            
            for(int i = 1 ; i < n ; i++) {
                if(i == 1) {    // 1번 열은 특수처리
                    dp[0][i] = dp[1][0] + arr[0][1];
                    dp[1][i] = dp[0][0] + arr[1][1];
                    continue;
                }
                
                dp[0][i] = Math.max(dp[1][i - 1], dp[1][i - 2]) + arr[0][i];
                dp[1][i] = Math.max(dp[0][i - 1], dp[0][i - 2]) + arr[1][i];
            }
            
            sb.append(Math.max(dp[0][n - 1], dp[1][n - 1])).append("\n");
        }
        
        System.out.println(sb);
    }
}
 

 

---

🧐 새로 알게 된 내용

저 dp 규칙을 찾고 점화식을 세우는 방법을 새로 깨닫다...

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[알고리즘] 백준 9465 스티커 -dp- 자바

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