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

 

 

https://www.acmicpc.net/problem/9465

9465번: 스티커

 

 

---

 

• 문제

 

 

---

 

• 문제 풀이

백준 9465 스티커는 2차원 배열을 이용한 DP (다이나믹 프로그래밍) 문제이다. 난이도는 실버 1로 측정되어 있다. DP 이론이 아직 부족한 사람은 밑에 있는 링크를 참고하면 되겠다.

 

https://propercoding.tistory.com/entry/알고리즘-다이나믹-프로그래밍-Dynamic-Programming

[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming)

이 문제에서 스티커는 2행 n열로 배치되어 있다. 따라서 배열을 만들 때 1차원 배열로 만드는 것보다 2차원 배열로 만들어서 풀면 더 수월하게 풀 수 있다. 그리고 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 문제에서 주어진 예제로 예시를 들어보겠다.

이 문제에서는 배열의 위치마다 값을 저장해야 하는 cost [][][][] 배열이 필요하고 이전 값과 합해서 최댓값을 만들기 위한 dp [][] 배열이 필요하다.

그리고 하나의 스티커를 뗄 때 올 수 있는 경우는 다음과 같다.

1. 자신의 왼쪽 대각선 (위의 배열일 경우 왼쪽 아래, 아래 배열일 경우 왼쪽 위)에 존재하는 값 다음에 올 수 있고

2. 자신의 왼쪽 왼쪽에 위치한 값 다음에 올 수 있다.

 

50	40	200	140	250
30	100	120	210	260

이 표에서 가장 높은 값, 즉 260이 답이 된다.

 

따라서 점화식으로 표현하면 다음과 같다.

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

 

---

 

• 코드

 

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));
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(br.readLine());
        for (int q = 0; q < t; q++) {
            int n = Integer.parseInt(br.readLine());
            int[][] cost = new int[2][n];
            int[][] dp = new int[2][n];
            StringTokenizer st1 = new StringTokenizer(br.readLine());
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                cost[0][i] = Integer.parseInt(st1.nextToken());
                cost[1][i] = 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 i = 1; i < n; i++) {
                if (i == 1) {
                    dp[0][i] = dp[1][0] + cost[0][1];
                    dp[1][i] = dp[0][0] + cost[1][1];
                    max = Math.max(dp[0][i], dp[1][i]);
                    continue;
                }
                dp[0][i] = Math.max(dp[1][i-1], dp[1][i-2]) + cost[0][i];
                dp[1][i] = Math.max(dp[0][i-1], dp[0][i-2]) + cost[1][i];
                max = Math.max(max, Math.max(dp[0][i], dp[1][i]));
            }
            sb.append(max + "\n");
        }
        System.out.print(sb);
    }
}

 

---

• 후기

 

이 문제는 그렇게 어렵지 않은 실버 1 수준의 DP 문제였다. 나의 개인적인 경험으로는 이런 유형의 DP 문제들을 풀 때 손으로 쓰면서 먼저 풀어보고 완벽하게 이해를 한 다음에 코드를 짠다. 바로 코드를 짜면 잘 안 풀리고 많이 복잡해지기도 하는 거 같다. 문제가 잘 안 풀리면 먼저 손으로 쓰면서 문제를 이해하고 푸는 것을 추천한다.