백준 9465. 스티커

문제 바로가기

스티커

문제 요약

스티커가 2행 n열로 배치되어있는데 스티커 한 장을 떼면 그 스티커의 상하좌우에 위치한 스티커는 모두 사용할 수 없다.

모든 스티커는 점수가 존재하고 그 점수가 최대가 될 수 있도록 스티커를 떼야한다. 이때, 최대 값을 구해보시요.

문제 풀이 포인트

이 문제의 경우 완탐으로 풀게 되면 n이 굉장히 커서 시간초과가 발생하는 문제이다. 따라서, 이문제는 dp를 활용해서 풀어야 하는 문제이다.

그렇다면 dp의 점화식은 어떻게 세우면 될까?

이 문제에서 가장 중요한 포인트는 그 스티커의 상하좌우는 모두 사용할 수 없다는 것이다. 그렇다는 말은 현재 위치에서 대각선 위 혹은 대각선 아래에 위치한 스티커의 사용 유무에 따라 현재 위치의 사용 유무가 결정된다는 말과 같다.

그렇다면, 대충 점화식의 형태가 나오는데, 대각선에 위치하고 있는 스티커중 몇번째까지가 현재 위치의 스티커에 영향을 주는지 확인해보면

현재 위치에서 왼쪽으로 2개까지의 대각선 방향의 스티커가 영향을 준다.

위의 그림에서, 임시로 첫번째 행의 노란색 화살표가 나오는 곳을 각각 1번과 2번, 두번째 행의 주황색 화살표가 나오는 곳을 3번과 4번이라 칭했을 때, 두 값이 각 화살표가 가르키는 위치의 스티커의 사용 유무를 결정 할 수 있다.

그렇다면, 같은 행의 2칸 전의 위치는 왜 고려를 하지 않는 것일까?

그 이유는 현재 위치에서 한칸 전의 상태를 떠올리면 된다. 현재는 3번째 열을 기준으로 그림을 그려놓은 상태지만, 2열의 상태 역시 그 이전의 열을 기준으로 dp 배열의 값을 결정하는데, 그때 대각선의 위치를 고려하기 때문에, 같은 행의 2칸 전의 위치는 고려할 필요가 없는 것이다.

그래서 각 위치의 점화식은

DP[0][i] = MAX(DP[1][i-1], DP[1][i-2]) + (현재 위치의 스티커 값)
DP[1][i] = MAX(DP[0][i-1], DP[0][i-2]) + (현재 위치의 스티커 값)

이 된다.

문제 코드[JAVA]

import java.util.*;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();
    while(T-- > 0) {
      int N = sc.nextInt();
      int[][] arr = new int[2][N+1];
      for(int i = 0; i < 2; i++) {
        for(int j = 1; j <= N; j++) {
          arr[i][j] = sc.nextInt();
        }
      }
      int[][] dp = new int[2][N+1];
      dp[0][1] = arr[0][1];
      dp[1][1] = arr[1][1];
      for(int i = 2; i <= N; i++) {
        dp[0][i] = Math.max(dp[1][i-2], dp[1][i-1]) + arr[0][i];
        dp[1][i] = Math.max(dp[0][i-2], dp[0][i-1]) + arr[1][i];
      }
      System.out.println(Math.max(dp[0][N], dp[1][N]));
    }
    sc.close();
  }
}