[백준 9465] 스티커(JAVA)

백준 9465번 문제 - 스티커

9465번: 스티커

---

문제 분석 

 

•  
• 하나의 스티커를 떼면 근처 (좌우상하) 스티커는 손상된다
• 스티커에는 점수가 있다.
• 어떻게 스티커를 뜯어야지 가장 높은 스티커 점수를 얻을 수 있을까?
• 최대 스티커 점수를 출력해라

 

---

해결 포인트

 

• DP 사용
• DP는 2차원 배열로 구현
  
  •  int [][] stikers = new int[2][N]; 
• 첫 열은 해당 스티커 점수로 고정
  • dp[0][0] : stikers[1][0] | dp[1][0] : stikers[1][0] 
• 첫번째 방법 : 전열 대각선 dp값 + 현재 스티커 값
  • dp[i][0] = dp[i-1][1] + stikers[i][0]  |  dp[i][1] = dp[i-1][0] +  stikers[i][1] 
  • 현재 스티커를 뜯기 위해서는 이전 열에서 다른 행의 스티커를 뜯을 경우만 해당된다고 판단

---

 

문제 발생 : 스티커를 이전 열에서는 안뜯는 경우도 존재 

 

현재 알고리즘으로는 위 스티커의 최대 점수로 240점이 된다.

 

하지만, 이 경우에는 이전 열에서 스티커를 안뜯어서 다음과 같이 320점이 된다.

---

• 두번째 방법  : 1개 전 열 대각선 dp값과 2개 전 열 같은 행 dp 값 중 큰 값 + 현재 스티커 값
  • Math.max(dp[(j + 1) % 2][i - 1], dp[(j + 1) % 2][i - 2]) + stikers[j][i] 

---

 

코드

 

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        for (int t = 0; t < T; t++) {
            int N = Integer.parseInt(br.readLine());

            int [][] stikers = new int[2][N];
            for (int i = 0; i < 2; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    stikers[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            int [][] dp = new int[2][N];
            dp[0][0] = stikers[0][0];
            dp[1][0] = stikers[1][0];
            if( N > 1) {
                dp[0][1] = dp[1][0] + stikers[0][1];
                dp[1][1] = dp[0][0] + stikers[1][1];
            }

            for (int i = 2; i < N; i++) {
                for (int j = 0; j < 2; j++) {
                    dp[j][i] = Math.max(dp[(j + 1) % 2][i - 1], dp[(j + 1) % 2][i - 2]) + stikers[j][i];
                }
            }

            bw.write(Math.max(dp[0][N-1], dp[1][N-1]) + "\n");
        }

        bw.flush();
        bw.close();
    }
}