[백준] 9465 : 스티커 - JAVA [자바]

안녕하세요.

오늘은 스티커 문제를 풀어보도록 하겠습니다.

 

 

📌 접근

다이나믹 프로그래밍을 이용해서 풀어야합니다.

점화식은 다음과 같이 세우면 됩니다.

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

 

 

풀이를 위해서는,

각 스티커의 비용을 저장하는 cost배열과

해당 스티커를 뗐을 때 누적 최대 점수를 저장하는 dp배열가 필요합니다.

 

 

dp[0][j] 구하기

빨간색 스티커의 위치를 dp[0][j]라고 가정해봅시다.

빨간색 스티커를 떼기 전에 가능한 case는 2가지 입니다.

 

 

 

 

 

 

 

case1) 직전에 dp[1][j-1]을 뗀 경우

 

 

 

case2) 직전에 dp[1][j-2]을 뗀 경우

 

 

 

 

 

 

 

 

 

💻 풀이

// hyeblee
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {

  /* dp[0][j]의 이전 선택하는 dp[1][j-1]과 dp[1][j-2]가 있다.
   *  dp[0][j-2]는 dp[1][j-1]의 이전 선택이 될 수도 있기 때문에 제외한다.
   *  <점화식>
   *  dp[0][j] = Math.max(dp[1][j-1], dp[1][j-2]) + cost[0][j]
   *  dp[1][j] = Math.max(dp[0][j-1], dp[0][j-2]) + cost[1][j] */

  public static int n;
  public static int[][] cost;
  public static int[][] dp;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

    for (int i = 0; i < t; i++) {
      n = Integer.parseInt(br.readLine());
      cost = new int[2][n];
      dp = new int[2][n];
      StringTokenizer st1 = new StringTokenizer(br.readLine());
      StringTokenizer st2 = new StringTokenizer(br.readLine());
      for (int j = 0; j < n; j++) {
        cost[0][j] = Integer.parseInt(st1.nextToken());
        cost[1][j] = Integer.parseInt(st2.nextToken());
      }
      dp[0][0] = cost[0][0];
      dp[1][0] = cost[1][0];
      int max = Math.max(dp[0][0], dp[1][0]);
      for (int j = 1; j < n; j++) {
        if (j == 1) { // 전전칸이 존재하지 않는 경우
          dp[0][1] = dp[1][0] + cost[0][j];
          dp[1][1] = dp[0][0] + cost[1][j];
          max = Math.max(dp[0][1], dp[1][1]);
          continue;
        }
        // 점화식에 dp[0][j-2]를 포함하지 않는 이유는 dp[1][j-1]의 이전선택일수도 있기 때문
        dp[0][j] = Math.max(dp[1][j - 1], dp[1][j - 2]) + cost[0][j];
        dp[1][j] = Math.max(dp[0][j - 1], dp[0][j - 2]) + cost[1][j];
        max = Math.max(max, Math.max(dp[0][j], dp[1][j]));
      }
      System.out.println(max);
    }

  }


}

 

🤔 고민했던 점 & 어려웠던 부분

dp[0][j]의 이전 선택에 dp[0][j-2]는 빠져야하는 것이 이해가 되지 않아서 풀이를 헤맸습니다.

 

 

dp[0][j-2] 은 dp[0][j]의 이전 선택으로 고려하지 않는 이유

 

dp[0][j-2]의 케이스는 고려하지 않습니다.

dp[1][j-1]의 직전 선택이 될 수 있기 때문입니다.