0%

[백준/9465] 스티커

작성일 Edited on In Disqus:

Baekjoon Online Judge - 9465

Review

  • 포도주 시식, 계단 오르기랑 비슷한 문제이다. 다른 점은 두 줄이라는 점.

  • 따라서 첫 번째 줄은 sticker[0][i], 두 번째 줄은 sticker[1][i] 이런 식으로 표현을 할 수 있다.

  • 규칙은 기준점에서 대각선에 있는 스티커의 점수만 더할 수 있다.

  • 하지만 문제는 두 칸, 세 칸 뒤의 대각선으로도 이동을 할 수 있다는 건데, 결론적으로는 두 칸까지의 이동만 비교하면 된다. 왜냐면 세 칸 뒤의 대각선은 이전 점수를 통해서 오는 게 더 높은 점수를 받을 수 있기 때문이다.

  • 따라서 경우는 총 두 가지

    1. 기준점에서 한 칸 뒤의 대각선으로 이동하는 경우
    2. 기준점에서 두 칸 뒤의 대각선으로 이동하는 경우

  • 각각의 경우를 점화식으로 나타내면 다음과 같다.

    1. dp[0][i] = Max(dp[1][i-1], dp[1][i-2]) + sticker[0][i]
    2. dp[1][i] = Max(dp[0][i-1], dp[0][i-2]) + sticker[1][i]

  • 첫 번째 줄에서 시작한 경우, 두 번째 줄에서 시작한 경우를 각각 구한 다음, 둘 중 큰 수를 출력하면 된다.

  • 여기서 sticker 배열은 스티커의 점수, dp 배열은 점수의 최대값을 저장한 배열이다.

  • 문제 푸는 것보다 입력 받는 게 더 까다로웠다.

Code (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.io.*;

public class Main {
  
  public static void main(String args[]) throws IOException{
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int T = Integer.parseInt(bf.readLine());
    
    while(T-- > 0) {
      int n = Integer.parseInt(bf.readLine());
      
      // 배열 선언
      int[][] dp = new int[2][100001];
      int[][] sticker = new int[2][100001];
      String[] str;
      
      // 스티커에 값 집어넣기
      for(int i = 0; i <= 1; i++) {
        str = bf.readLine().split(" ");
        for(int j = 1; j <= n; j++) {
          sticker[i][j] = Integer.parseInt(str[j-1]);
        }
      }
      
      // 첫 번째 값 넣어주기
      // (이동이 없으니 sticker의 첫 번째 값을 dp 배열에 넣어줌)
      dp[0][1] = sticker[0][1];
      dp[1][1] = sticker[1][1];
      
      // 값 비교해서 각 배열에 넣어주기
      for(int i = 2; i <= n; i++) {
        dp[0][i] = Math.max(dp[1][i-1], dp[1][i-2]) + sticker[0][i];
        dp[1][i] = Math.max(dp[0][i-1], dp[0][i-2]) + sticker[1][i];
      }
      
      System.out.println(Math.max(dp[0][n], dp[1][n]));  
    }
    
  }
  
}